Clifford A. Shaffer 数据结构教材的快速排序详解

本文最后更新于 684 天前，其中的信息可能已经有所发展或是发生改变。

近日学习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）那样的示意图，能够更加直观地描述该回溯到哪一层，如下图。

代码解释

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

主函数是这样的：

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里。这个函数是这样的：

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向左向右移动的过程。

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，可以输入自己的样例，分步观察排序过程；在它的下方，有一个小练习，可以手动模拟过程，检验学习效果。

This content is licensed under a Creative Commons Attribution-ShareAlike 4.0 International license.

算法思想与过程

示例

代码解释

附录

发送评论 编辑评论

发送评论编辑评论