Quicksort

最近公司打算招一个新的程序，之前我们的策略一直是只面试并没有笔试题。我想了下笔试题最好不要过于偏重于哪一门语言或者哪一方面的知识，那么最好的就是大学学习的基本知识，包括算法和数据结构等，我也打算让面试者在面试过程中实际写一些代码。因为，通过聊天来判断一个人能力是否合格太虚了。基于此原因，我自己事先去复习了一下快速排序（Quicksort）的知识，并且实现了好几个快速排序的算法，这里会简单介绍 3 个重要的快速排序算法。

1 简介

Robert Sedgewick（《算法》的作者，书写的非常好，当然人肯定是大牛）称快速排序是 20 世纪最重要的 10 个算法之一，快速排序几乎被用于任何重要的系统排序（system sorts）中，被许多语言标准库作为默认排序算法实现，比如 C 语言中 qsort 就是典型的例子。

快速排序最早由 Tony Hoare 于 1959 年发现的，后期经过了不断的发展、论证得到了许多别的优化方案。在恰当实现的情况下，其性能是归并排序（Mergesort）和堆排序（Heapsort）的 2~3 倍。

快速排序是一种比较排序算法，能够对任何支持 less then 关系的数据进行排序，它不是一种稳定排序（stable sort），意味着相等的元素的相对位置可能会发生改变。对于额外的内存需求很少，这种特定也叫就地排序（in-place sort）。计算机科学家对快速排序做了相当多的研究，在数学上的分析得到平均比较次数是 O(n log n) ，最坏的情况是 O(n^2) 次比较。

2 历史

了解历史对于使用算法会有一个更好的理解，知道前辈在其上花费的精力，有过怎样的思考、争论才打到当前的局面。《未来简史》有句话：知道历史，让我们做更自由的人。了解历史的过程本身就是一件很有意思的事。

Tony Hoare 在 1959 年做一个机器文本翻译工作时，需要一个排序算法使得在查字典前将所有的文本都排好序，然后直接查字典就行了。开始他尝试使用插入排序，结果太慢了，然后很快就想到了新算法——Quicksort。等他做完这个项目回到英国时，他的老板跟他打赌 10 便士说“你这个算法肯定没有 shellsort 快”，可想而知，Hoare 赢了。其后再 Hoare 学习了 ALGOL 语言之后，他能够使用递归将他的快速排序算法发表在当时的顶尖计算机科学杂志上。因而，也获得了 1980 的图灵奖。

Robert Sedgewick 的博士论文就是以快速排序作为研究对象，解决了快速排序的选择轴点（pivot）的问题，对比较和交换次数做了数学推导。Bentley 和 Mcllroy 两位合作干了很多事情，包括处理排序中大量相等元素问题和九分选取轴点方案。Bentley 在他的《编程珠玑》中介绍了 Lomuto 的快速排序算法，称之为比 Hoare 的快速排序更简单且更容易实现对。他说“我用了 Hoare 的版本好几年都没有真正理解它”，可见即便是最聪明的科学家也有难以理解的东西。Lomuto 版本还被《算法导论》这本书作为快速排序算法介绍了，因而比较流行。但是，相对于 Hoare 的版本性能上更差一些。

2009 年 Yaroslavskiy （名字这么奇怪肯定不是英语的名字）提出了双轴点（dual pivot）快速排序实现，并且最终被 Java 7 运行时作为新的默认排序算法。可见快速排序是多么的重要，应用之广。

3 算法

快速排序算法的思想并不难，用几句话就可以概括，不过实现方法确实多种多样，我以前还见过完全不用递归的写法。快速排序本质上是分治算法（Divide and Conquer Algorithm），将一个长序列分成较小部分和较大部分两个子序列，然后再以递归方式排序子序列。以下是步骤：

选一个元素作为轴点（pivot），选取的方法很多简单的直接选任意端点，还有选端点和中点的中位数，最复杂的是将序列分成 3 段，分别取它们的中位数，再从这三个中位数中取一个中位数作为轴点，这样做的原因在于提升轴点的平衡性；
分段（Partition）：将序列进行重排序，使得所有比轴点大的元素都在右边，比轴点小的元素都在左边，（与轴点相等的元素可以任意在左右）这样轴点的位置就是确定的。
递归处理分段中得到的较小部分和较大部分，递归的 base case 是序列中只有一个元素或者没有元素，最终得到一个完整的排好序的序列；

轴点的选择和分段有很多不同的实现方式，不同的方式之间会有很大的性能差异。

3.1 Lomuto 的版本

它是选右端点 hi 作为轴点，Lomuto 的版本在于分段的实现方法不同。他用索引 i 来保存所有小于轴点的最大索引，用 j 来遍历整个数组，这样当遇到小于轴点的元素时就将它交换到 i 的下一个位置（是一个大于或等于轴点的数），然后递增 i。这样结束之后 lo 到 i （包含）就是较小部分，i+1 到 hi-1（包含）就是较大部分。具体如下伪代码：

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p - 1 )
        quicksort(A, p + 1, hi)

algorithm partition(A, lo, hi) is
    pivot := A[hi]
    i := lo - 1    
    for j := lo to hi - 1 do
        if A[j] < pivot then
            i := i + 1
            swap A[i] with A[j]
    if A[hi] < A[i + 1] then
        swap A[i + 1] with A[hi]
    return i + 1

3.2 Hoare 的版本

Hoare 的版本选取轴点的位置会影响到算法的实现，如果选择了 lo 点的话，就不能让较小部分为空，否则就进入了无限循环。我在实现的时候就遇到了这个问题。这里描述的实现方法就是让轴点为 lo ，分段算法跟 Lomuto 的有较大区别。他用到了 i 和 j 从两边向对面遍历，如果 i 遇到大于或等于轴点的元素，并且 j 遇到了小于或等于轴点的元素就交换，直到 i 和 j 相遇。[lo..j] 是较小部分，[j+1..hi] 是较大部分。伪代码如下：

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p)
        quicksort(A, p + 1, hi)

algorithm partition(A, lo, hi) is
    pivot := A[lo]
    i := lo - 1
    j := hi + 1
    loop forever
        do
            i := i + 1
        while A[i] < pivot

        do
            j := j - 1
        while A[j] > pivot

        if i >= j then
            return j

        swap A[i] with A[j]

4 实现问题

关于怎样选择轴点，上面算法部分已经描述过了。它们主要就是为了让已经排好序的序列也能够有一个足够好的排序时间。在最早的时候就是选取最左边或者最右边的作为轴点，后来发展成随机选取一个元素作为轴点，选取中点作为轴点，以及前中后的中位数（median-of-three, Mo3）和三段中位数成为 ninther，就是上面描述的分成三段分别取中位数再递归取新的中位数。公式如下：

ninther(a) = median(Mo3(first 1/3 of a), Mo3(middle 1/3 of a), Mo3(final 1/3 of a))

除此之外，在实现中还得考虑到整数溢出的情况，如：(lo + hi) / 2 可能会溢出，用 lo + (hi - lo) / 2 代替来取的中点的索引，我在 glibc 中就看到过这个用法。

还有就是重复元素的问题，如果有很多重复的元素，很可能会导致算法时间是 O(n^2)，这是不可接受的。上面的两种算法都没有将值等于轴点的元素特殊对待。为了解决这个问题（也称为 Dutch national flag problem），发明先的实现方式：将序列分成小于部分、等于部分和大于部分，Bentley 称之为 fat partition。这种算法也叫做 3-way partitioning 。伪代码如下：

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := pivot(A, lo, hi)
        left, right := partition(A, p, lo, hi)  // note: multiple return values
        quicksort(A, lo, left - 1)
        quicksort(A, right + 1, hi)

三路分段目前我用到了两个版本，一个是 Bentley-McIroy 的版本，将左边遇到的等于轴点值元素都放到最右边，右边的放到最右边，等 i 和 j 相遇之后在它们放回到中间位置。

C 代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


int i = l-1, j=r, p = l-1, q = r;
Item pivot = a[r];
for (;;)
{
    while (a[++i] < pivot) ;
    while (a[--j] > pivot) if (j == l) break;
    if (i >= j) break;
    exch(a, i, j);
    if (a[i] == pivot) { p++; exch(a, p, i); }
    if (a[j] == pivot) { q--; exch(a, q, j); }
}

exch(a, i, r);
j = i-1;
i = i+1;
for (int k=l; k<p; k++, j--)   exch(a, k, j);
for (int k=r-1; k>q; k--, i++) exch(a, k, i);

另一种是 Dijkstra 的实现，轴点选 lo 点的值，用 i 从左到右遍历，lt 在左端点表示所有小于轴点的最大索引，gt 在又端点表示所有大于轴点的最小索引。i 在遍历的过程遇到小于轴点的元素就与 lt 交换，lt 和 i 都自增1；遇到大于轴点的元素就与 gt 交换，gt 自减1，再次检查；遇到等于轴点的元素就直接越过；