一、概述
排序是将一组数据元素序列重新排列，使得数据元素序列按某个数据项（关键字）有序。不管是在数据处理中，还是别的应用场景中，对数据的排序都是很有必要的。对于任意的数据元素序列，若排序前后所有相同关键字的相对位置不变，则称该排序算法为稳定的排序方法，否则为不稳定的排序方法。例如对下面数据做排序操作：
3, 2, 3, 4 -> 2, 3, 3, 4
带下划线的3的位置发生了变化，则该排序方法是不稳定的。
二、冒泡排序
冒泡排序是将相邻两个关键字对比，若为 a1>a2 则进行交换，然后依次比较后面的数据，直到最后，每一趟冒泡排序，都会确定最大的关键字记录并放至最后。假设我们有一组数据 4,6,3,5,1,2，对它进行冒泡排序过程如下：
算法实现代码如下：
public static int[] bubbleSort(int[] a) { for (int i = 0; i < a.length - 1; i++) { for (int j = 0; j < a.length - i - 1; j++) { if (a[j] > a[j + 1]) { int tmp = a[j]; a[j] = a[j + 1]; a[j + 1] = tmp; } } } return a; }
根据上面代码可以计算出时间复杂度如下：
(n-1) + (n-2) + ... + (n-i) + ... + 1 = n(n-1)/2
所以时间复杂度为 O(n^2)，只使用一个临时变量，空间复杂度为 O(1)。
三、选择排序
选择排序是从无序的序列中选择关键字最小或最大的记录，并将它加入到有序的子序列中，如果我们每次选择最小的记录，每进行一趟排序，就会确定最小的关键字并放至最前。假设我们有一组数据 4,6,3,5,1,2，对它进行选择排序过程如下：
算法实现代码如下：
public static int[] selectSort(int[] a) { for (int i = 0; i < a.length - 1; i++) { for (int j = i + 1; j < a.length; j++) { if (a[i] > a[j]) { int tmp = a[j]; a[j] = a[i]; a[i] = tmp; } } } return a; }
根据上面代码可以计算出时间复杂度如下：
(n-1) + (n-2) + ... + (n-i) + ... + 1 = n(n-1)/2
所以时间复杂度为 O(n^2)，只使用一个临时变量，空间复杂度为 O(1)。
四、插入排序
插入排序是将无序的数据序列中的一个或几个记录插入到有序子序列中，从而增加有序子序列的长度。每一趟排序都会确定最小的关键字并放至最前。假设我们有一组数据 4,6,3,5,1,2，对它进行插入排序过程如下：
算法实现代码如下：
public static int[] insertSort(int[] a) { int tmp; for (int i = 1; i < a.length; i++) { int j = i - 1; tmp = a[i]; for (; j >= 0 && tmp < a[j]; j--) { a[j + 1] = a[j]; } a[j + 1] = tmp; } return a; }
根据上面代码可以计算出时间复杂度如下：
n + (n-1) + (n-2) + ... + (n-i) + ... + 2 = (n+2)(n-1)/2
所以时间复杂度为 O(n^2)，只使用一个临时变量，空间复杂度为 O(1)。
五、归并排序
归并排序是将两个或两个以上的有序表组合成一个新的有序表，我们在进行归并排序时会将数据元素序列，按照 n/2 的长度递归拆分，然后再两两合并，每一个合并的操作都只是对于两个有序表进行合并，直至得到一个长度为 n 的有序序列为止。假设我们有一组数据 4,6,3,5,1,2，对它进行归并排序过程如下：
算法实现代码如下：
public static int[] mergeSort(int[] a, int l, int r) { if (l < r) { int m = (l + r) / 2; mergeSort(a, l, m); mergeSort(a, m + 1, r); merge(a, l, m, r); } return a; } private static void merge(int[] a, int l, int m, int r) { int n1 = m - l + 1; int n2 = r - m; int[] L = new int[n1]; int[] R = new int[n2]; System.arraycopy(a, l, L, 0, n1); System.arraycopy(a, m + 1, R, 0, n2); int i = 0, j = 0, k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { a[k++] = L[i++]; } else { a[k++] = R[j++]; } } while (i < n1) { a[k++] = L[i++]; } while (j < n2) { a[k++] = R[j++]; } }
根据上面代码可以得出，每一趟归并的时间复杂度为 O(n)，总共需要归并 log2n 趟，因而总的时间复杂度为 O(n*log n)，在归并的过程中，需要一个与数据表等长的数组空间，因此，空间复杂度为 O(n)。
六、快速排序
快速排序是实际使用中已知的最快的算法，快速排序在数据元素中选择一个数据元素为枢纽，然后把比它小的放前面，比它大的放后面，这样分成两堆，然后对两个小堆做同样的操作，以此类推，直到不能分为止，最后返回最终排序结果，快速排序的设计，关键在于枢纽的选择。假设我们有一组数据 4,6,3,5,1,2，选择第一个关键字作为枢纽，对它进行快速排序过程如下：
算法实现代码如下：
public static int[] quicklySort(int[] a, int l, int r) { if (l >= r) { return a; } int i = l, j = r, k = a[l]; while (i != j) { while (i < j && a[j] > k) { j--; } a[i] = a[j]; while (i < j && a[i] <= k) { i++; } a[j] = a[i]; a[i] = k; } quicklySort(a, l, j - 1); quicklySort(a, j + 1, r); return a; }
如果每次总是选到中间值作为枢纽，那快速排序可以达到最好的情况，时间复杂度为 O(n*log n)，如果每次总是选到最小或最大值作为枢纽，最坏情况时间复杂度为 O(n^2)。对应的空间复杂度最坏情况为 O(n)，平均情况为 O(log n)。
读者可以去网上找资料，了解快速排序中确定枢纽位置的相关算法。
七、总结
五种排序算法对比
| 算法 | 冒泡排序 | 选择排序 | 插入排序 | 归并排序 | 快速排序 |
| 稳定性 | 稳定 | 不稳定 | 稳定 | 稳定 | 不稳定 |
| 平均时间复杂度 | O(n^2) | O(n^2) | O(n^2) | O(n*log n) | O(n*log n) |
| 最坏时间复杂度 | O(n^2) | O(n^2) | O(n^2) | O(n*log n) | O(n^2) |
| 空间复杂度 | O(1) | O(1) | O(1) |
递归与分治策略
前面讲到的归并排序和快速排序，都使用到了分治策略，为了解决一个规模较大的问题，我们可以将其分解成两个子问题，并借助递归分别得到它们的解，然后将子问题的解合并成原问题的解，这就是分治策略。我们把一个规模大的问题，分解成 k 个子问题，对这 k 个子问题分别求解，如果子问题的规模仍然不够小，则再划分为 k 个子问题，如此递归的进行下去，直到问题的规模足够小，很容易求出其解为止。
