近日学习 Clifford A. Shaffer 的《数据结构与算法分析》（Data Structure and Algorithm Analysis）的快速排序算法部分，深感例子的难懂，遂决定自己写一个这本书快速排序算法的详解。

算法思想与过程

Shaffer 在本节的一开始说了这么一段话：

Before we get to Quicksort, consider for a moment the practicality of using a
Binary Search Tree for sorting. You could insert all of the values to be sorted into
the BST one by one, then traverse the completed tree using an inorder traversal.
The output would form a sorted list. This approach has a number of drawbacks,
including the extra space required by BST pointers and the amount of time required
to insert nodes into the tree. However, this method introduces some interesting
ideas. First, the root of the BST (i.e., the first node inserted) splits the list into two
sublists: The left subtree contains those values in the list less than the root value
while the right subtree contains those values in the list greater than or equal to the
root value. Thus, the BST implicitly implements a “divide and conquer” approach
to sorting the left and right subtrees. Quicksort implements this concept in a much
more efficient way.

Data Structure and Algorithm Analysis Edition 3.2 (C++ version), Page 245

他提到了二叉搜索树（BST），这是一种前序遍历结果有序的树结构。对于 BST 的每一颗子树来说，根节点左子树的元素都比它小，右子树中的元素都比它大，这样一来根节点元素的位置就是确定的了。

BST 用的是一种分治的思想，也就是对于一个节点的左右子树，要么为空，要么仍然是一颗 BST。使用这样的递归定义，我们就可以构建出一棵二叉搜索树。对于一个要构建为二叉搜索树的区间，先随意确定一个根节点的值。这样做虽然可能影响效率，但也可以构建一棵完整的 BST。然后，将小于它的值放到左子树中，将大于它的值放到右子树中。然后再对这两边分别进行构建，如此重复。

但是，二叉搜索树总是有结构性时间空间消耗的，于是就有人想到把它 “拍扁”，于是诞生了快速排序：

Quicksort first selects a value called the pivot. (This is conceptually like the
root node’s value in the BST.) Assume that the input array contains k values less
than the pivot. The records are then rearranged in such a way that the k values
less than the pivot are placed in the first, or leftmost, k positions in the array, and
the values greater than or equal to the pivot are placed in the last, or rightmost,
n−k positions. This is called a partition of the array. The values placed in a given
partition need not (and typically will not) be sorted with respect to each other. All
that is required is that all values end up in the correct partition. The pivot value itself
is placed in position k. Quicksort then proceeds to sort the resulting subarrays now
on either side of the pivot, one of size k and the other of size n − k − 1. How are
these values sorted? Because Quicksort is such a good algorithm, using Quicksort
on the subarrays would be appropriate.

Data Structure and Algorithm Analysis Edition 3.2 (C++ version), Page 245

也就是说，每次排序都确定下来一个元素在本轮待排序列中的位置（称为 “枢轴”/“pivot”），也就是确定了这个元素在整个序列中的位置，然后将枢轴两边（不含枢轴）直到本轮序列两端的部分分别再进行一次快速排序。对位置不合适的元素，成对地进行交换，这样就可以保证一边小一边大了。

每轮排序的目的都是确定一个元素（即枢轴）的位置，几轮分治下来就能够把所有元素的位置全部确定下来。

枢轴和根节点，对左右两边排序和对左右两边建树，到这里你应该能感觉到理念比较像了吧。只不过建 BST 时是从数组中建，可以直接将数分到左子树区域和右子树区域；排序时不占用额外空间，所以要找到一对位置不正确的才能交换，而且枢轴的位置并不是那么固定。

更具体来说，在这本书中，选择（左边界 + 右边界）/2 的位置为枢轴，先将其与最后一个元素交换，然后再将枢轴前的元素分辨大小；最后，再将枢轴以交换的方式移至正确的位置。

听不明白？上例子！

示例

下面我们使用蓝色字体表示某层回溯的排序范围，用红色加粗字体表示枢轴，用橙色表示 i，用黄色表示 j。

这是一个有 9 个元素的例子。

初始的排序序列为 [0,8]，选择枢轴为第 5 个元素 7.。

为了将 7 移到最后，我们交换 7 和 53。

因为小于 7 的数应该待在左边，从 64 开始往前，找第一个小于 7 的数。然而并没有，于是 j 指向了 31。

然后 i 从 31 开始准备往右遍历，找比 7 大的数，可惜一开始 i 和 j 就交叉了。i 和 j 交叉的地方，就是枢轴应该待的位置。

好，现在交换 31 和 7。

7 的位置已经确定了，因为左边根本没有元素，接下来排序的范围就是右边的 [1,8]。确定枢轴为 53。

将 53 与最后一个元素 31 交换。

从 73 开始找第一个大于 53 的数，是 73；从 64 开始找第一个小于 53 的数，是 22。

交换 73 和 22。

继续往左往右找，直到 i 找到了 73。

i 和 j 重合，那就将对应元素与枢轴 53 交换。

53 也到了序列中它应该待的位置，先对原序列 53 左边的 [1,5] 进行排序。选择 13 作为枢轴。

将 13 与 28 交换。

从左边找第一个大于 13 的数，是 22；从右边找第一个小于 13 的数，发现没有，于是 i 和 j 又在下标 1 即 22 处相遇了。

交换 22 和 13。

13 到了最终位置。左边没有元素，所以对 [2,5] 进行排序。选择 28 作为枢轴。

将 28 与 22 交换。

从左边找第一个大于 28 的数，为 44；从右边找第一个小于 28 的数，为 22。

将 44 与 22 交换。

从 22 再找比 28 大的数，没找到，在 44 的位置 i 与 j 重合。

将 28 与枢轴 44 交换。

现在 28 到了最终位置。

因为 28 左边只有一个元素，这部分肯定是有序的，22 就该在这个位置；于是对 [4,5] 进行快速排序，选取枢轴为 31。

将 31 与 44 交换。

从 44 找比 31 大和比 31 小的数，但是因为除枢轴就 44 一个数，i 和 j 当然会在 44 相遇。

交换 44 和 31。

于是 31 到了最终的位置，左边没有元素，右边只有 44，所以分治到了最小的范围，不可以再分治下去。

（顺便提一句题外话：从这里可以看出快速排序在元素很少的时候效率比较低，所以如果希望优化快排的话，可以搞一个在元素小的时候换插排）

一路回溯，最终我们回到了刚刚确定 53 位置的时候，那时的状态是这样的。排序范围 [1,8]，枢轴 53。

排序区间中，枢轴 53 的左边已经排序完成，而右边没变，还没轮到排序。下面我们就排 [7,8]。选取 64 为枢轴。

将 64 与序列尾部的 73 交换。

照例移动 i 和 j，当然毫无悬念地会在 73 重合。

将 73 和 64 交换。

至此，64 归位，左边没有元素，右边只有 73，所以 [7,8] 排序完成。

回溯，发现这已经是最后一块未排序区间了，所以全部数都已经排序完成。

在研究快速排序的回溯过程时，也可以选择使用教材图 7-14（英文版 P248）那样的示意图，能够更加直观地描述该回溯到哪一层，如下图。

代码解释

有了上面对算法本身的理解，我相信理解代码应该不是很大的困难了。

主函数是这样的：

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

template <typename E, typename Comp>
void qsort(E A[], int i, int j) { // Quicksort
if (j <= i) return; // Don’t sort 0 or 1 element
int pivotindex = findpivot(A, i, j);
swap(A, pivotindex, j); // Put pivot at end
template <typename E, typename Comp>
void qsort(E A[], int i, int j)
{ // Quicksort
    if (j <= i)
        return; // Don’t sort 0 or 1 element
    int pivotindex = findpivot(A, i, j);
    swap(A, pivotindex, j); // Put pivot at end
    // k will be the first position in the right subarray
    int k = partition<E, Comp>(A, i - 1, j, A[j]);
    swap(A, k, j); // Put pivot in place
    qsort<E, Comp>(A, i, k - 1);
    qsort<E, Comp>(A, k + 1, j);
}

它首先检验了排序区域，如果长度小于等于 1，则没必要进行排序，直接 return。

然后，使用 findpivot 函数确定枢轴，保存在 pivotindex 里。这个函数是这样的：

1
2
3
4
5

template <typename E>
inline int findpivot(E A[], int i, int j)
{
    return (i + j) / 2;
}

简单来说，就是取整个区间中间位置的值来返回。这么说的话，好像根本没必要传进 A 数组……

之后，用 swap(A,pivotindex,j); 语句来将 j 与区间内最后一个元素交换。

后面调用的 partition 函数，执行的就是 i 和 j 向左向右移动的过程。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

template <typename E, typename Comp>
inline int partition(E A[], int l, int r, E &pivot)
{
    do
    { // Move the bounds inward until they meet
        while (Comp::prior(A[++l], pivot))
            ; // Move l right and
        while ((l < r) && Comp::prior(pivot, A[--r]))
            ;          // r left
        swap(A, l, r); // Swap out-of-place values
    } while (l < r);   // Stop when they cross
    return l;          // Return first position in right partition
}

这里的 Comp 类内含一个比较函数，能够比较两个对象的大小，如果前面的比后面小则返回 true。

当 A[i] 小于枢轴值的时候向右移，这样就会停在第一个比枢轴大（或相等）的数上；这之后，当 A[j] 大于枢轴值且没有越过 l 的时候向左移，于是停在 i 上或者从右往左第一个比枢轴小的数上。

极端情况下，如果枢轴就是最大的，那么 i 和 j 就会停在枢轴上；如果枢轴是最小的，那就会停在最左边。

然后，将 i 和 j 相遇的位置返回，记为 k，它就是枢轴所应该呆在的位置。执行 swap，将枢轴换上来。

这之后执行二分，分别将当前区间的枢轴左半边和枢轴右半边作为新区间进行快速排序操作即可。

附录

这里推荐一个工具，能够用动画形式展示自定义例子的快速排序过程：OpenDSA - 快速排序（英文）。它的内容与 Shaffer 的教材基本相同，毕竟 Shaffer 先生就是 Virginia Tech 的教授。

向下翻到 Quicksort Visualization，可以输入自己的样例，分步观察排序过程；在它的下方，有一个小练习，可以手动模拟过程，检验学习效果。