首先来一张效率图对比下：

一、冒泡法

排序算法，大家用过或者写得最多就是冒泡算法了吧，就是临近的数字两两比较，用两层循环来比较。这样，第一趟（外循环）完后最小或者最大的值就到了最前面，形象点就是小泡泡浮了起来。这个不用多介绍了，直接上代码：

//冒泡排序
void maoPaoSort(int array[]){for (int i = 0; i < N-1; i++){for (int j = 0; j < N-1-i; j++){if (array[j] > array[j+1]){int temp = array[j+1];array[j+1] = array[j];array[j] = temp;}}printf("this is %d:", i + 1);printArray(array);}
}

   选择排序，即找到最小元素，并记录其位置，然后和第i个元素进行交换，每次进行一个循环便找到一个最小值。

   比如在一个长度为N的无序数组中，在第一趟遍历N个数据，找出其中最小的数值与第一个元素交换，第二趟遍历剩下的N-1个数据，找出其中最小的数值与第二个元素交换......第N-1趟遍历剩下的2个数据，找出其中最小的数值与第N-1个元素交换，至此选择排序完成。

以下面5个无序的数据为例：

56 12 80 91 20（文中仅细化了第一趟的选择过程）

第1趟：12 56 80 91 20

第2趟：12 20 80 91 56

第3趟：12 20 56 91 80

第4趟：12 20 56 80 91

代码如下：

void choiceSort(int array[]){for (int i = 0; i < N; i++){int k = i;for (int j = k + 1; j < N; j++){if (array[j] < array[k]){k = j;}}//找到了最小的值再交换int temp = array[i];array[i] = array[k];array[k] = temp;}
}

三、插入排序

比较容易理解的是它的工作原理与抓扑克牌一样，对于抓到的未排序的牌，从后往前逐个比较，找到相应位置并插入。插入过程中需要把已排序元素不断往后移。

第一趟比较示图：

具体算法描述如下：

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5

void insertSort(int array[]){//从第二个元素开始，加入第一个元素是已排序数组for (int i = 1; i < N; i++){//待插入元素 array[i]if (array[i] < array[i - 1]){int wait = array[i];int j = i;while (j > 0 && array[j - 1] > wait){//从后往前遍历已排序数组，若待插入元素小于遍历的元素，则遍历元素向后挪位置array[j] = array[j - 1];j--;}array[j] = wait;}}
}

这里引荐一篇大牛的文章，看了简直是醍醐灌顶，哈哈，坐在马桶上看算法：快速排序

假设我们现在对“6  1  2 7  9  3  4  5 10  8”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数（不要被这个名词吓到了，就是一个用来参照的数，待会你就知道它用来做啥的了）。为了方便，就让第一个数6作为基准数吧。接下来，需要将这个序列中所有比基准数大的数放在6的右边，比基准数小的数放在6的左边，类似下面这种排列：

3  1  2 5  4  6  9 7  10  8

在初始状态下，数字6在序列的第1位。我们的目标是将6挪到序列中间的某个位置，假设这个位置是k。现在就需要寻找这个k，并且以第k位为分界点，左边的数都小于等于6，右边的数都大于等于6。想一想，你有办法可以做到这点吗？

排序算法显神威

方法其实很简单：分别从初始序列“6  1  2 7  9  3  4  5 10  8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边（即i=1），指向数字6。让哨兵j指向序列的最右边（即=10），指向数字。

具体代码如下：

void quickSort(int array[], int left, int right){if (left > right){return;}int i, j, temp;i = left;j = right;//以最左边的数作为基准数temp = array[left];while (i != j){//先从右边开始找小于temp的元素  注意等号while (array[j] >= temp && i < j) {j--;}//再从左边开始找大于temp的元素while (array[i] <= temp && i < j){i++;}//左右哨兵均找到满足要求的数后，交换这两个数if (i < j){int change = array[i];array[i] = array[j];array[j] = change;}}//i==j  将基准数归位，此时基准数左边的数均小于基准数，右边的数均大于基准数array[left] = array[j];array[j] = temp;//然后递归处理基准左边未排序的数，和基准右边的数quickSort(array, left, i-1);quickSort(array, i + 1, right);}

五、归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，归并排序将两个已排序的表合并成一个表。首先是将待排序数组逐步分割，直至单个元素作为一个数列。然后开始归并，首先就是元素单个比较，比如元素a[0]和a[1]比较，a[2]和a[3]比较，这样下来就有N/2个排好序的子序列。依次递归操作，最后合并成一个数组。就大功告成了。

缺点：需要分配额外的空间

图解如下

看成是 n 个有序的子序列（长度为 1），然后两两归并。

得到 n/2 个长度为2 或 1 的有序子序列。继续亮亮归并

最后一趟

代码如下：

//************************归并排序*******************
void merge(int array[], int low, int mid, int high){//i 遍历第一区间[low mid]int i = low;//j 遍历第二区间[mid+1 high]int j = mid + 1;int *temp = new int[high - low + 1];if (!temp){printf("malloc memory failed.\n");}int count = 0;while (i <= mid && j <= high){//依次比较两个区间较小的数，然后装入temp数组if (array[i] <= array[j]){//取等号temp[count++] = array[i++];}else{temp[count++] = array[j++];}}//比较完成后，假如第一区间还有剩余，继续装载while (i <= mid){temp[count++] = array[i++];}//比较完成后，假如第一区间还有剩余，继续装载while (j <= high){temp[count++] = array[j++];}//将归并排好序的元素赋值给原数组for (int i = low,k=0; i <= high; i++,k++){array[i] = temp[k];}delete []temp;printf("Merge Number:low:%d  mid:%d  mid+1:%d  high:%d.\n", low, mid, mid + 1, high);}void cutSortArray(int array[],int low,int high){//分割数组，一分为2，二分为四，，，int mid = (low + high) / 2;if (low < high){cutSortArray(array, low, mid);cutSortArray(array, mid + 1, high);merge(array, low, mid, high);}
}

int _tmain(int argc, _TCHAR* argv[])
{int testArray[N] = {0};//如果不设置随机数种子，rand()在调用时会自动设随机数种子为1，每次执行时是相同的srand( (unsigned) time(NULL) );for (int i = 0; i < N; i++){testArray[i] = rand()%30;}printf("Origin Array:\n");printArray(testArray);printf("Guibing Sort Array:\n");cutSortArray(testArray,0,N-1);printArray(testArray);return 0;
}

六：希尔排序