冒泡排序、插入排序、选择排序这三种排序算法的时间复杂度都是 O(n2)，比较高，适合小规模数据的排序。下面讲解两种时间复杂度为 O(nlogn) 的排序算法：归并排序和快速排序，它们更适合大规模的数据排序。

是原地排序？ 是否稳定？ 最好 最坏 平均
归并排序 ❌ ✅ O(nlogn) O(nlogn) O(nlogn)
快速排序 ✅ ❌ O(nlogn) O(n2) O(nlogn)

归并排序

归并排序（Merge Sort）的核心是分治思想。分治就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。如果要排序一个数组，我们可以先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。
1.png
从图中可以看到，分治思想跟递归思想很像，实际上，分治算法一般都是用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧，这两者并不冲突。写递归代码的技巧就是，分析得出递推公式，然后找到终止条件，最后将递推公式翻译成递归代码。所以，要想写出归并排序的代码，我们先写归并排序的递推公式。

  1. 递推公式：
  2. merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))
  4. 终止条件：
  5. p >= r 不用再继续分解
  • merge_sort(p…r) 表示，给下标从 p 到 r 之间的数组排序。我们将这个排序问题转化为了两个子问题，merge_sort(p…q) 和 merge_sort(q+1…r)，其中下标 q 等于 p 和 r 的中间位置，即 (p+r)/2。当 A[p…q] 和 A[q+1…r] 这两个子数组都排好序之后，我们再将两个有序的子数组合并在一起，这样 A[p…r] 之间的数据就也排好序了。
  • merge 函数的作用就是，将已经有序的 A[p…q] 和 A[q+1…r] 合并成一个有序的数组，并且放入 A[p…r]。

动画演示：
mergeSort.gif

1. 代码实现

merge 函数的实现思路
如下图所示，我们申请一个临时数组 tmp，大小与 A[p…r] 相同。我们用两个游标 i 和 j，分别指向 A[p…q] 和 A[q+1…r] 的第一个元素。比较这两个元素 A[i] 和 A[j]，如果 A[i] <= A[j]，我们就把 A[i] 放入到临时数组 tmp，并且 i 后移一位，否则将 A[j] 放入到数组 tmp，j 后移一位。

继续上述比较过程，直到其中一个子数组中的所有数据都放入临时数组中，再把另一个数组中的数据依次加入到临时数组的末尾，此时临时数组中存储的就是两个子数组合并之后的结果了。最后再把临时数组 tmp 中的数据拷贝到原数组 A[p…r] 中就完成了 merge 的过程。
image.png
代码实现

  1. public static int[] sort(int[] array) {
  2.     mergeSortInternally(array, 0, array.length - 1);
  3.     return array;
  4. }
  6. /**
  7.  * 分解
  8.  */
  9. private static void mergeSortInternally(int[] array, int start, int end) {
  10.     // 递归终止条件
  11.     if (start >= end) {
  12.         return;
  13.     }
  14.     // 取中间位置,防止(start + end)的和超过int类型最大值
  15.     int middle = start + (end - start) / 2;
  16.     mergeSortInternally(array, start, middle);
  17.     mergeSortInternally(array, middle + 1, end);
  18.     merge(array, start, middle, end);
  19. }
  21. /**
  22.  * 对array数组的 [start-middle]、[(middle+1)-end] 部分进行合并排序
  23.  */
  24. private static void merge(int[] array, int start, int middle, int end) {
  25.     int[] tmp = new int[end - start + 1];
  26.     int i = start;
  27.     int j = middle + 1;
  28.     int k = 0;
  29.     // 比较
  30.     while (i <= middle && j <= end) {
  31.         if (array[i] < array[j]) {
  32.             tmp[k++] = array[i++];
  33.         } else {
  34.             tmp[k++] = array[j++];
  35.         }
  36.     }
  37.     // 判断哪个子数组中有剩余的数据，就将剩余的数据拷贝到临时数组tmp中
  38.     if (i <= middle) {
  39.         while (i <= middle) {
  40.             tmp[k++] = array[i++];
  41.         }
  42.     } else {
  43.         while (j <= end) {
  44.             tmp[k++] = array[j++];
  45.         }
  46.     }
  47.     // 将tmp数组中的数据拷贝回array
  48.     for (int i1 = 0; i1 <= end - start; i1++) {
  49.         array[start + i1] = tmp[i1];
  50.     }
  51. }

2. 性能分析

归并排序是稳定的排序算法吗？
归并排序稳不稳定关键要看 merge() 函数，也就是两个有序子数组合并成一个有序数组的那部分代码。在合并的过程中，如果 A[p…q] 和 A[q+1…r] 之间有值相同的元素，我们可以先把 A[p…q] 中的元素放入 tmp 数组。这样就保证了值相同的元素，在合并前后的先后顺序不变。所以，归并排序是一个稳定的排序算法。

归并排序的时间复杂度是多少？
归并排序涉及递归，递归的适用场景是，一个问题 a 可以分解为多个子问题 b、c，那求解问题 a 就可以分解为求解问题 b、c。问题 b、c 解决之后，我们再把 b、c 的结果合并成 a 的结果。如果我们定义求解问题 a 的时间是 T(a)，求解问题 b、c 的时间分别是 T(b) 和 T( c)，那我们就可以得到这样的递推关系式：

  1. T(a) = T(b) + T(c) + K

其中 K 等于将两个子问题 b、c 的结果合并成问题 a 的结果所消耗的时间。套用这个公式，我们来分析一下归并排序的时间复杂度。假设对 n 个元素进行归并排序需要的时间是 T(n)，那分解成两个子数组排序的时间都是 T(n/2)。merge() 函数合并两个有序子数组的时间复杂度是 O(n)。所以，归并排序的时间复杂度计算公式为：

  1. T(1) = C；                         n=1时，只需要常量级的执行时间，所以表示为C。
  2. T(n) = 2*T(n/2) + n；     n>1
  4. # 对公式进行推导
  5. T(n) = 2*T(n/2) + n
  6.      = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
  7.      = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
  8.      = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
  9.      ......
  10.      = 2^k * T(n/2^k) + k * n
  11.      ......

通过推导，我们可以得到 T(n) = 2k * T(n/2k) + kn。当 T(n/2k) = T(1) 时，也就是 n/2k = 1，我们得到 k=log2n。我们将 k 值代入上面的公式，得到 T(n)=Cn+nlog2n 。用大 O 标记法表示为 T(n) = O(nlogn)，所以归并排序的时间复杂度是 O(nlogn)。归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况时间复杂度都是 O(nlogn)。

归并排序的空间复杂度是多少？
归并排序的时间复杂度任何情况下都是 O(nlogn)，看起来非常优秀。但归并排序并没有像快排那样应用广泛，是因为它有一个致命弱点，就是归并排序不是原地排序算法。因为归并排序在合并两个有序数组为一个有序数组时需要借助额外的存储空间。那归并排序的空间复杂度到底是多少呢？

实际上，递归代码的空间复杂度并不能像时间复杂度那样累加。尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。

快速排序

快速排序（Quicksort）算法利用的也是分治思想，但它和归并排序的思路完全不一样。快排的核心思想是：如果要对 A[p…r] 进行排序，我们选择 A[p…r] 之间的任意一个数据作为 pivot（分区点）。遍历 A[p…r] 之间的数据，将小于 pivot 的放左边，将大于 pivot 的放右边，将 pivot 放中间。经过这一步骤之后，A[p…r] 就被分成了三个部分，前面 [p…q-1] 之间都是小于 pivot 的，中间是 pivot，后面 [q+1…r] 之间是大于 pivot 的。
image.png
根据分治、递归的处理思想，我们可以用递归来排序 [p…q-1] 之间的数据和 [q+1…r] 之间的数据，直到区间缩小为 1，就说明所有的数据都有序了。如果我们用递推公式来将上面的过程写出来的话，就是这样：

  1. 递推公式：
  2. quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1… r)
  4. 终止条件：
  5. p >= r

将递推公式转化成递归代码，用伪代码来实现：

  1. // 快速排序，A是数组，n表示数组的大小
  2. quick_sort(A, n) { 
  3.     quick_sort_c(A, 0, n-1)
  4. }
  5. // 快速排序递归函数，p,r为下标
  6. quick_sort_c(A, p, r) {
  7.     if p >= r then return 
  8.       q = partition(A, p, r) // 获取分区点，并完成对A的分区
  9.       quick_sort_c(A, p, q-1) 
  10.       quick_sort_c(A, q+1, r)
  11. }

1. 代码实现

归并排序中有一个 merge() 合并函数，而快速排序有一个 partition() 分区函数。partition() 分区函数实际上就是随机选择一个元素作为 pivot（一般可以选择 [p…r] 区间的最后一个元素），然后对 A[p…r] 分区，函数返回 pivot 的下标。如果不考虑空间消耗，partition() 分区函数可以写得非常简单。我们可以申请两个临时数组 X 和 Y，遍历 A[p…r]，将小于 pivot 的元素都拷贝到临时数组 X，将大于 pivot 的元素都拷贝到临时数组 Y，最后再将数组 X 和数组 Y 中数据顺序拷贝到 A[p…r]。
image.png
但是，如果按照这种思路实现的话，partition() 函数就需要很多额外的内存空间，那么快排就不是原地排序算法了。如果我们希望快排是原地排序算法，那它的空间复杂度得是 O(1)，那我们就需要在 A[p…r] 的原地完成分区操作。原地分区函数的实现思路非常巧妙，伪代码如下：

  1. partition(A, p, r) {
  2.   pivot := A[r]
  3.   i := p
  4.   for j := p to r-1 do {
  5.     if A[j] < pivot {
  6.       swap A[i] with A[j]
  7.       i := i+1
  8.     }
  9.   }
  10.   swap A[i] with A[r]
  11.   return i

这里的处理有点类似选择排序。我们通过游标 i 把 A[p…r-1] 分成两部分。A[p…i-1] 的元素都是小于 pivot 的，我们暂且称为已处理区间，A[i…r-1] 是未处理区间。我们每次都从未处理的区间 A[i…r-1] 中取一个元素 A[j] 与 pivot 对比，如果小于 pivot，则将其加入到已处理区间的尾部，也就是 A[i] 的位置。在实际插入时，我们不需要移动数组元素，通过将 A[i] 与 A[j] 交换，就可以在 O(1) 时间复杂度内将 A[j] 放到下标为 i 的位置。
image.png
因为分区的过程涉及交换操作，如果数组中有两个相同的元素，比如序列 6，8，7，6，3，5，9，4，在经过第一次分区操作之后，两个 6 的相对先后顺序会改变。所以快速排序并不是一个稳定的排序算法。

代码实现

  1. public static void sort(int[] array) {
  2.     quickSortInternally(array, 0, array.length - 1);
  3. }
  5. /**
  6.  * 分区,在分区的过程中会根据pivot进行排序
  7.  */
  8. private static void quickSortInternally(int[] array, int start, int end) {
  9.     if (start >= end) {
  10.         return;
  11.     }
  12.     // 获取分区点,按照pivot进行递归
  13.     int pivot = partition(array, start, end);
  14.     quickSortInternally(array, start, pivot - 1);
  15.     quickSortInternally(array, pivot + 1, end);
  16. }
  18. /**
  19.  * 对 array[start…end] 分区，并返回分区后的pivot的下标
  20.  */
  21. private static int partition(int[] array, int start, int end) {
  22.     // 取最后一个元素作为分区点，这样便于区分已处理区间和未处理区间
  23.     int pivot = array[end];
  24.     // i表示已处理区间
  25.     int i = start;
  26.     // j表示未处理区间，循环取未处理区间中的元素与分区点比较，看是否要放入已处理区间
  27.     for (int j = start; j < end; j++) {
  28.         if (array[j] < pivot) {
  29.             // 将未处理区间元素与已处理区间最后一个元素交换
  30.             if (i != j) {
  31.                 int temp = array[i];
  32.                 array[i] = array[j];
  33.                 array[j] = temp;
  34.             }
  35.             // 已处理区间里的元素数量加一
  36.             i++;
  37.         }
  38.     }
  39.     // 交换分区点位置
  40.     int temp = array[i];
  41.     array[i] = array[end];
  42.     array[end] = temp;
  43.     return i;
  44. }

2. 性能分析

上面在讲解快排的实现原理时，已经分析了稳定性和空间复杂度。快排是一种原地、不稳定的排序算法。现在我们来看下快排的时间复杂度。

快排也是用递归来实现的。如果每次分区操作，都能正好把数组分成大小接近相等的两个小区间，那快排的时间复杂度递推求解公式跟归并是相同的。所以，快排的最好情况时间复杂度是 O(nlogn)。

  1. T(1) = C；   n=1时，只需要常量级的执行时间，所以表示为C。
  2. T(n) = 2*T(n/2) + n； n>1

但是，公式成立的前提是每次分区操作，我们选择的 pivot 都很合适，正好能将大区间对等地一分为二。但实际上这种情况是很难实现的。举一个比较极端的例子，如果数组中的数据已经是有序的了，比如 1，3，5，6，8。我们每次选择最后一个元素作为 pivot，那每次分区得到的两个区间都是不均等的。我们需要进行大约 n 次分区操作，才能完成快排的整个过程。这种情况下，快排的时间复杂度就从 O(nlogn) 退化成了 O(n2) 了。

上面两个极端情况下的时间复杂度，一个是分区极其均衡，一个是分区极其不均衡。它们分别对应快排的最好情况时间复杂度和最坏情况时间复杂度。那平均情况时间复杂度是多少呢？快排在大部分情况下的时间复杂度都可以做到 O(nlogn)，只有在极端情况下才会退化到 O(n2)。因此快排的平均情况时间复杂度是 O(nlogn)。

3. 优化快速排序

上面讲到，如果数据原来就是有序的或者接近有序的，每次分区点都选择最后一个数据，那快速排序算法就会变得非常糟糕，时间复杂度会退化为 O(n2)。实际上，出现这种情况的主要原因是分区点选择不够合理。

最理想的分区点是：被分区点分开的两个分区中的数据量是差不多的。如果很粗暴地直接选择第一个或最后一个数据作为分区点而不考虑数据特点的话，那么很可能会发生快排的时间复杂度退化为 O(n2) 的情况。为了提高快排的性能，我们要尽可能地让每次分区都比较平均。这里介绍两种比较常用、简单的分区算法。

1）三数取中法
我们从区间的首、尾和中间分别取一个数，然后对比大小，取这三个数的中间值作为分区点。这样每间隔某个固定的长度，取数据出来比较，将中间值作为分区点的分区算法，肯定要比单纯取某一个数据更好。但如果要排序的数组比较大，那三数取中可能就不够了，可能要“五数取中”或“十数取中”了。

2）随机法
随机法就是每次从要排序的区间中，随机选择一个元素作为分区点。这种方法并不能保证每次分区点都选的比较好，但是从概率的角度来看，也不大可能会出现每次分区点都选得很差的情况，所以平均情况下，这样选的分区点是比较好的。时间复杂度退化为最糟糕的 O(n2) 的情况，出现的可能性不大。

区别

归并排序和快速排序是两种稍微复杂的排序算法，它们用的都是分治的思想，代码都通过递归来实现，过程非常相似。理解归并排序的重点是理解递推公式和 merge() 合并函数。同理，理解快排的重点也是理解递推公式，还有 partition() 分区函数。
image.png

  • 归并排序的处理过程是由下到上的，先处理子问题，然后再合并，在合并的过程中进行排序。而快排正好相反，它的处理过程是由上到下的，先分区，在分区的过程中进行排序，然后再处理子问题。

  • 归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但它是非原地排序算法，主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。快速排序算法虽然最坏情况下的时间复杂度是 O(n2)，但是平均情况下时间复杂度都是 O(nlogn)。不仅如此，快速排序算法时间复杂度退化到 O(n2) 的概率非常小，我们可以通过合理地选择 pivot 来避免这种情况。