排序算法也是面试中常常提及的内容，问的最多的应该是快速排序、堆排序。这些排序算法很基础，但是如果平时不怎么写代码的话，面试的时候总会出现各种 bug。虽然思想都知道，但是就是写不出来。本文打算对各种排序算法进行一个汇总，包括插入排序、冒泡排序、选择排序、计数排序、归并排序，基数排序、桶排序、快速排序等。快速排序比较重要，会单独写一篇，而堆排序见本系列的二叉堆那篇文章即可。
需要提到的一点就是：插入排序，冒泡排序，归并排序，计数排序都是稳定的排序，而其他排序则是不稳定的。本文完整代码在 这里。
1.插入排序插入排序是很基本的排序，特别是在数据基本有序的情况下，插入排序的性能很高，最好情况可以达到O(N)，其最坏情况和平均情况时间复杂度都是 O(N^2)。代码如下：
/** * 插入排序 */ void insertSort(int a[], int n) { int i, j; for (i = 1; i < n; i++) { /* * 循环不变式：a[0...i-1]有序。每次迭代开始前，a[0...i-1]有序， * 循环结束后i=n，a[0...n-1]有序 * */ int key = a[i]; for (j = i; j > 0 && a[j-1] > key; j--) { a[j] = a[j-1]; } a[j] = key; } } 复制代码2.希尔排序希尔排序内部调用插入排序来实现，通过对 N/2，N/4...1阶分别排序，最后得到整体的有序。
/** * 希尔排序 */ void shellSort(int a[], int n) { int gap; for (gap = n/2; gap > 0; gap /= 2) { int i; for (i = gap; i < n; i++) { int key = a[i], j; for (j = i; j >= gap && key < a[j-gap]; j -= gap) { a[j] = a[j-gap]; } a[j] = key; } } } 复制代码3.选择排序选择排序的思想就是第 i 次选取第 i 小的元素放在位置 i。比如第 1 次就选择最小的元素放在位置 0，第 2 次选择第二小的元素放在位置 1。选择排序最好和最坏时间复杂度都为 O(N^2)。代码如下：
/** * 选择排序 */ void selectSort(int a[], int n) { int i, j, min, tmp; for (i = 0; i < n-1; i++) { min = i; for (j = i+1; j < n; j++) { if (a[j] < a[min]) min = j; } if (min != i) tmp = a[i], a[i] = a[min], a[min] = tmp; //交换a[i]和a[min] } } 复制代码循环不变式：在外层循环执行前，a[0...i-1]包含 a 中最小的 i 个数，且有序。
初始时，i=0，a[0...-1] 为空，显然成立。
每次执行完成后，a[0...i] 包含 a 中最小的 i+1 个数，且有序。即第一次执行完成后，a[0...0] 包含 a 最小的 1 个数，且有序。
循环结束后，i=n-1，则 a[0...n-2]包含 a 最小的 n-1 个数，且已经有序。所以整个数组有序。
4.冒泡排序冒泡排序时间复杂度跟选择排序相同。其思想就是进行 n-1 趟排序，每次都是把最小的数上浮，像鱼冒泡一样。最坏情况为 O(N^2)。代码如下：
/** * 冒泡排序-经典版 */ void bubbleSort(int a[], int n) { int i, j, tmp; for (i = 0; i < n; i++) { for (j = n-1; j >= i+1; j--) { if (a[j] < a[j-1]) tmp = a[j], a[j] = a[j-1], a[j-1] = tmp; } } } 复制代码循环不变式：在循环开始迭代前，子数组 a[0...i-1] 包含了数组 a[0..n-1] 的 i-1 个最小值，且是排好序的。
对冒泡排序的一个改进就是在每趟排序时判断是否发生交换，如果一次交换都没有发生，则数组已经有序，可以不用继续剩下的趟数直接退出。改进后代码如下：
/** * 冒泡排序-优化版 */ void betterBubbleSort(int a[], int n) { int tmp, i, j; for (i = 0; i < n; i++) { int sorted = 1; for (j = n-1; j >= i+1; j--) { if (a[j] < a[j-1]) { tmp = a[j], a[j] = a[j-1], a[j-1] = tmp; sorted = 0; } } if (sorted) return ; } } 复制代码5.计数排序假定数组为 a[0...n-1] ，数组中存在重复数字，数组中最大数字为k，建立两个辅助数组 b[] 和 c[]，b[] 用于存储排序后的结果，c[] 用于存储临时值。时间复杂度为 O(N)，适用于数字范围较小的数组。
计数排序原理如上图所示，代码如下：
/** * 计数排序 */ void countingSort(int a[], int n) { int i, j; int *b = (int *)malloc(sizeof(int) * n); int k = maxOfIntArray(a, n); // 求数组最大元素 int *c = (int *)malloc(sizeof(int) * (k+1)); //辅助数组 <span>for</span> (i = 0; i <= k; i++) c[i] = 0; <span>for</span> (j = 0; j < n; j++) c[a[j]] = c[a[j]] + 1; //c[i]包含等于i的元素个数 <span>for</span> (i = 1; i <= k; i++) c[i] = c[i] + c[i-1]; //c[i]包含小于等于i的元素个数 <span>for</span> (j = n-1; j >= 0; j--) { // 赋值语句 b[c[a[j]]-1] = a[j]; //结果存在b[0...n-1]中 c[a[j]] = c[a[j]] - 1; } /*方便测试代码，这一步赋值不是必须的*/ <span>for</span> (i = 0; i < n; i++) { a[i] = b[i]; } free(b); free(c);}
复制代码