《编程珠玑》之快速排序

1. 一种简单的快速排序

快速排序最重要的就是partition函数，即选定某一个数后，使得所有小于该数的数字都在其左侧，大于该数的数字都在其右侧。本节给出的算法过程如下：

我们将需要划分的目标区间定位[l, u]。
首先给定目标值t = x[l]。我们需要重新组织x[l...u]，使得所有小于t的元素都在m的一端，所有大于t的元素在m的另一端。
初始时m = l，我们将i从l+1一直遍历到u，代码在检测第i个元素时必须考虑两种情况。如果x[i]>=t，那么一切正常，不变式为真；如果x[i]<t，可以通过使m增加1（指向小元素的新位置）重新获得不变式，然后交换x[i]和x[m]。

完整代码如下：

void qsort1(int nums[], int l, int u) {
    if (l < u) {
        int m = l;
        for (int i = l + 1; i <= u; i++) {
            int num = nums[i];
            if (num < nums[l]) {
                swap(nums[++m], nums[i]);
            }
        }
        swap(nums[m], nums[l]);
        myqsort(nums, l, m - 1);
        myqsort(nums, m + 1, u);
    }
}

2. 更好的几种快速排序

qsort1函数能够快速完成对随机整数数组的排序，但是在非随机的输入上它的性能如何呢？我们不妨采用一种极端的情况：n个相同元素组成的数组，对于这种输入，插入排序的性能非常好：每个元素需要移动的距离都为0；但是qsort1函数的性能却非常糟糕。n-1次划分中每次划分都需要O(n)时间来去掉一个元素，所以总的运行时间为O(n²)。使用双向划分可以避免这种情况。

下标i和j初始化为待划分数组的两端。主循环中有两个内循环，第一个内循环将i向右移过小元素，遇到大元素时停止；第二个内循环将j向左移过大元素，遇到小元素时停止。然后主循环测试这两个下标是否交叉并交换它们的值。这样做虽然交换的次数增加了，但却将所有元素都相同的最坏情况变成了差不多需要nlog2n次比较的最好情况，实现代码如下：

void qsort2(int nums[], int l, int u) {
    if (l < u) {
        int i = l + 1;
        int j = u;
        int t = nums[l];
        while (i <= j) {
            while (i <= u && nums[i] < t) {
                i++;
            }
            
            while (nums[j] > t) {
                j--;
            }
            if (i <= j) {
                swap(nums[i], nums[j]);
            }
        }
        swap(nums[l], nums[j]);
        qsort2(nums, l, j - 1);
        qsort2(nums, j + 1, u);
    }
}

到目前为止我们看到的快速排序都是围绕数组的第一个元素进行划分的。对于随机输入，这样做没问题；但对于某些常见输出，这种做法需要的时间和空间都偏多。例如，虽然数组已经按升序排好了，那么它就会先围绕最小的元素进行划分，然后是第二小的元素，以此类推，总共需要O(n²)的时间。随机选择划分元素就可以得到好得多的性能，我们通过把x[l]与x[l...u]中的一个随机项相交换来实现这一点：

swap(l, randint(l, u));

我们的快速排序花费了大量的时间来排序很小的子数组。如果用插入排序之类的简单方法来排序这些很小的子数组，程序的速度会很快。我们将qsort2中的第一个if语句改为：

if (u - l >= cutoff)

其中cutoff是一个小整数。程序结束后，数组并不是有序的，而是被组合成一块一块随机排列的值，并且满足这样的条件：某一块中的元素小于它右边任何块中的元素。我们必须通过另一种排序算法对块的内部进行排序。由于数组是几乎有序的，因此插入排序比较适用。