Quick Sort - 快速排序

核心：快排是一种采用分治思想的排序算法，大致分为三个步骤。

  1. 定基准——首先随机选择一个元素最为基准
  2. 划分区——所有比基准小的元素置于基准左侧，比基准大的元素置于右侧
  3. 递归调用——递归地调用此切分过程

out-in-place - 非原地快排

容易实现和理解的一个方法是采用递归，使用 Python 的 list comprehension 实现如下所示：

  1. #!/usr/bin/env python
  4. def qsort1(alist):
  5.     print(alist)
  6.     if len(alist) <= 1:
  7.         return alist
  8.     else:
  9.         pivot = alist[0]
  10.         return qsort1([x for x in alist[1:] if x < pivot]) + \
  11.                [pivot] + \
  12.                qsort1([x for x in alist[1:] if x >= pivot])
  14. unsortedArray = [6, 5, 3, 1, 8, 7, 2, 4]
  15. print(qsort1(unsortedArray))

输出如下所示：

  1. [6, 5, 3, 1, 8, 7, 2, 4]
  2. [5, 3, 1, 2, 4]
  3. [3, 1, 2, 4]
  4. [1, 2]
  5. []
  6. [2]
  7. [4]
  8. []
  9. [8, 7]
  10. [7]
  11. []
  12. [1, 2, 3, 4, 5, 6, 7, 8]

『递归 + 非原地排序』的实现虽然简单易懂，但是如此一来『快速排序』便不再是最快的通用排序算法了，因为递归调用过程中非原地排序需要生成新数组，空间复杂度颇高。list comprehension 大法虽然好写，但是用在『快速排序』算法上就不是那么可取了。

复杂度分析

在最好情况下，快速排序的基准元素正好是整个数组的中位数，可以近似为二分，那么最好情况下递归的层数为 \log n, 咋看一下每一层的元素个数都是 n, 那么空间复杂度为 O(n) 无疑了，不过这只答对了一半，从结论上来看是对的，但分析方法是错的。

首先来看看什么叫空间复杂度——简单来讲可以认为是程序在运行过程中所占用的存储空间大小。那么对于递归的 out-in-place 调用而言，排除函数调用等栈空间，最好情况下，每往下递归调用一层，所需要的存储空间是上一层中的一半。完成最底层的调用后即向上返回执行出栈操作，故并不需要保存每层所有元素的值。所以需要的总的存储空间就是
\sum _{i=0} ^{} \frac {n}{2^i} = 2n

不是特别理解的可以结合下图的非严格分析和上面 Python 的代码，递归调用的第一层保存8个元素的值，那么第二层调用时实际需要保存的其实仅为4个元素，逐层往下递归，而不是自左向右保存每一层的所有元素。

那么在最坏情况下 out-in-place 需要耗费多少额外空间呢？最坏情况下第 i 层需要 i - 1 次交换，故总的空间复杂度：

\sum_{i=0}^n (n-i+1) = O(n^2)

Quicksort Recursive

in-place - 原地快排

one index for partition

先来看一种简单的 in-place 实现，仍然以[6, 5, 3, 1, 8, 7, 2, 4]为例，结合下图进行分析。以下标 l 和 u 表示数组待排序部分的下界(lower bound)和上界(upper bound)，下标 m 表示遍历到数组第 i 个元素时当前 partition 的索引，基准元素为 t, 即图中的 target.

Quick Sort one index for partition

在遍历到第 i 个元素时，x[i] 有两种可能，第一种是 x[i] \geq t, i 自增往后遍历；第二种是 x[i] < t, 此时需要将 x[i] 置于前半部分，比较简单的实现为 swap(x[++m], x[i]). 直至 i == u 时划分阶段结束，分两截递归进行快排。既然说到递归，就不得不提递归的终止条件，容易想到递归的终止步为 l >= u, 即索引相等或者交叉时退出。使用 Python 的实现如下所示：

Python

  1. #!/usr/bin/env python
  4. def qsort2(alist, l, u):
  5.     print(alist)
  6.     if l >= u:
  7.         return
  9.     m = l
  10.     for i in xrange(l + 1, u + 1):
  11.         if alist[i] < alist[l]:
  12.             m += 1
  13.             alist[m], alist[i] = alist[i], alist[m]
  14.     # swap between m and l after partition, important!
  15.     alist[m], alist[l] = alist[l], alist[m]
  16.     qsort2(alist, l, m - 1)
  17.     qsort2(alist, m + 1, u)
  19. unsortedArray = [6, 5, 3, 1, 8, 7, 2, 4]
  20. print(qsort2(unsortedArray, 0, len(unsortedArray) - 1))

Java

  1. public class Sort {
  2.     public static void main(String[] args) {
  3.         int unsortedArray[] = new int[]{6, 5, 3, 1, 8, 7, 2, 4};
  4.         quickSort(unsortedArray);
  5.         System.out.println("After sort: ");
  6.         for (int item : unsortedArray) {
  7.             System.out.print(item + " ");
  8.         }
  9.     }
  11.     public static void quickSort1(int[] array, int l, int u) {
  12.         for (int item : array) {
  13.             System.out.print(item + " ");
  14.         }
  15.         System.out.println();
  17.         if (l >= u) return;
  18.         int m = l;
  19.         for (int i = l + 1; i <= u; i++) {
  20.             if (array[i] < array[l]) {
  21.                 m += 1;
  22.                 int temp = array[m];
  23.                 array[m] = array[i];
  24.                 array[i] = temp;
  25.             }
  26.         }
  27.         // swap between array[m] and array[l]
  28.         // put pivot in the mid
  29.         int temp = array[m];
  30.         array[m] = array[l];
  31.         array[l] = temp;
  33.         quickSort1(array, l, m - 1);
  34.         quickSort1(array, m + 1, u);
  35.     }
  37.     public static void quickSort(int[] array) {
  38.         quickSort1(array, 0, array.length - 1);
  39.     }
  40. }

容易出错的地方在于当前 partition 结束时未将 i 和 m 交换。比较alist[i]和alist[l]时只能使用<而不是<=! 因为只有取<才能进入收敛条件，<=则可能会出现死循环，因为在=时第一个元素可能保持不变进而产生死循环。

相应的结果输出为：

  1. [6, 5, 3, 1, 8, 7, 2, 4]
  2. [4, 5, 3, 1, 2, 6, 8, 7]
  3. [2, 3, 1, 4, 5, 6, 8, 7]
  4. [1, 2, 3, 4, 5, 6, 8, 7]
  5. [1, 2, 3, 4, 5, 6, 8, 7]
  6. [1, 2, 3, 4, 5, 6, 8, 7]
  7. [1, 2, 3, 4, 5, 6, 8, 7]
  8. [1, 2, 3, 4, 5, 6, 7, 8]
  9. [1, 2, 3, 4, 5, 6, 7, 8]

Two-way partitioning

对于仅使用一个索引进行 partition 操作的快排对于随机分布数列的效果还是不错的，但若数组本身就已经有序或者相等的情况下，每次划分仅能确定一个元素的最终位置，故最坏情况下的时间复杂度变为 O(n^2). 那么有什么办法尽可能避免这种最坏情况吗？聪明的人类总是能找到更好地解决办法——使用两个索引分别向右向左进行 partition.

先来一张动图看看使用两个索引进行 partition 的过程。

Quick Sort two index for partition

  1. 选中3作为基准
  2. lo指针指向元素6, hi指针指向4, 移动lo直至其指向的元素大于等于3, 移动hi直至其指向的元素小于3。找到后交换lo和hi指向的元素——交换元素6和2。
  3. lo递增，hi递减，重复步骤2，此时lo指向元素为5, hi指向元素为1. 交换元素。
  4. lo递增，hi递减，发现其指向元素相同，此轮划分结束。递归排序元素3左右两边的元素。

对上述过程进行适当的抽象：

  1. 下标 $$i$$ 和 $$j$$ 初始化为待排序数组的两端。
  2. 基准元素设置为数组的第一个元素。
  3. 执行 partition 操作，大循环内包含两个内循环：
    • 左侧内循环自增 $$i$$, 直到遇到不小于基准元素的值为止。
    • 右侧内循环自减 $$j$$, 直到遇到小于基准元素的值为止。
  4. 大循环测试两个下标是否相等或交叉，交换其值。

这样一来对于数组元素均相等的情形下，每次 partition 恰好在中间元素，故共递归调用 \log n 次，每层递归调用进行 partition 操作的比较次数总和近似为 n. 故总计需 n \log n 次比较。[^programming_pearls]

Python

  1. #!/usr/bin/env python
  4. def qsort3(alist, lower, upper):
  5.     print(alist)
  6.     if lower >= upper:
  7.         return
  9.     pivot = alist[lower]
  10.     left, right = lower + 1, upper
  11.     while left <= right:
  12.         while left <= right and alist[left] < pivot:
  13.             left += 1
  14.         while left <= right and alist[right] >= pivot:
  15.             right -= 1
  16.         if left > right:
  17.             break
  18.         # swap while left <= right
  19.         alist[left], alist[right] = alist[right], alist[left]
  20.     # swap the smaller with pivot
  21.     alist[lower], alist[right] = alist[right], alist[lower]
  23.     qsort3(alist, lower, right - 1)
  24.     qsort3(alist, right + 1, upper)
  26. unsortedArray = [6, 5, 3, 1, 8, 7, 2, 4]
  27. print(qsort3(unsortedArray, 0, len(unsortedArray) - 1))

Java

  1. public class Sort {
  2.     public static void main(String[] args) {
  3.         int unsortedArray[] = new int[]{6, 5, 3, 1, 8, 7, 2, 4};
  4.         quickSort(unsortedArray);
  5.         System.out.println("After sort: ");
  6.         for (int item : unsortedArray) {
  7.             System.out.print(item + " ");
  8.         }
  9.     }
  11.     public static void quickSort2(int[] array, int l, int u) {
  12.         for (int item : array) {
  13.             System.out.print(item + " ");
  14.         }
  15.         System.out.println();
  17.         if (l >= u) return;
  18.         int pivot = array[l];
  19.         int left = l + 1;
  20.         int right = u;
  21.         while (left <= right) {
  22.             while (left <= right && array[left] < pivot) {
  23.                 left++;
  24.             }
  25.             while (left <= right && array[right] >= pivot) {
  26.                 right--;
  27.             }
  28.             if (left > right) break;
  29.             // swap array[left] with array[right] while left <= right
  30.             int temp = array[left];
  31.             array[left] = array[right];
  32.             array[right] = temp;
  33.         }
  34.         /* swap the smaller with pivot */
  35.         int temp = array[right];
  36.         array[right] = array[l];
  37.         array[l] = temp;
  39.         quickSort2(array, l, right - 1);
  40.         quickSort2(array, right + 1, u);
  41.     }
  43.     public static void quickSort(int[] array) {
  44.         quickSort2(array, 0, array.length - 1);
  45.     }
  46. }

相应的输出为：

  1. [6, 5, 3, 1, 8, 7, 2, 4]
  2. [2, 5, 3, 1, 4, 6, 7, 8]
  3. [1, 2, 3, 5, 4, 6, 7, 8]
  4. [1, 2, 3, 5, 4, 6, 7, 8]
  5. [1, 2, 3, 5, 4, 6, 7, 8]
  6. [1, 2, 3, 5, 4, 6, 7, 8]
  7. [1, 2, 3, 4, 5, 6, 7, 8]
  8. [1, 2, 3, 4, 5, 6, 7, 8]
  9. [1, 2, 3, 4, 5, 6, 7, 8]
  10. [1, 2, 3, 4, 5, 6, 7, 8]
  11. [1, 2, 3, 4, 5, 6, 7, 8]

从以上3种快排的实现我们可以发现其与『归并排序』的区别主要有如下两点：

  1. 归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序。递归调用发生在处理整个数组之前。
  2. 快速排序将一个数组分成两个子数组并对这两个子数组独立地排序，两个子数组有序时整个数组也就有序了。递归调用发生在处理整个数组之后。

Robert Sedgewick 在其网站上对 Quicksort 做了较为完整的介绍，建议去围观下。

Reference