2.1 快速排序

第二卷开篇，我们讲工业界用得最多的排序——快速排序（Quicksort）。它和归并排序（1.2）一样是分治，但分治的姿势恰好相反：归并是"无脑对半切、重点在合"，快排是"重点在切、合起来不费吹灰之力"。理解了这个对照，你就抓住了分治的两种典型形态。快排还是随机化算法的第一个例子，下一篇的线性选择会更深地用到这个思想。

1.快排的分治：重点在"切"

回忆归并排序：它不管元素大小，机械地把数组对半切，所以"分"很省事，但"合"（归并）要花 $\Theta(n)$ 仔细比较合并。

快排反过来。它的"分"（叫 partition，划分）是重头戏：选一个元素做基准（pivot），把数组重排成"比基准小的放左边、比基准大的放右边、基准放中间"。这一刀下去，基准就归位了——它恰好落在排序后该在的位置上。然后左边、右边各自递归快排。至于"合"——根本不用合，因为划分时元素就已经各就各位了。

QUICKSORT(A, p, r)
    if p < r:
        q = PARTITION(A, p, r)   // 基准归位到 q
        QUICKSORT(A, p, q-1)      // 排左边
        QUICKSORT(A, q+1, r)      // 排右边

2.划分：一次扫描让基准归位

整个算法的灵魂在 PARTITION。它选一个基准（通常取最后一个元素 $A[r]$ ），然后用一根指针把数组扫一遍，维护一个不变量："左段全 $\le$ 基准，右段全 $>$ 基准"。

PARTITION(A, p, r)
    x = A[r]                 // 基准
    i = p - 1                // 左段的右边界
    for j = p to r-1:
        if A[j] <= x:        // 小的归到左段
            i = i + 1
            swap(A[i], A[j])
    swap(A[i+1], A[r])       // 基准放到左右段之间
    return i + 1             // 基准的最终位置

这一遍扫描下来，比基准小的全挤到左边了，基准被换到 $i+1$ 这个位置——它左边全比它小、右边全比它大，于是它就是排序后的第 $i+1-p$ 小，归位完成。

3.复杂度：平均 $O(n\log n)$ ，最坏 $O(n^2)$

快排的复杂度强烈依赖"切得多均匀"，这点和归并排序很不一样。

最坏情况：每次基准都选到最大或最小值，划分极度失衡（一边 $n-1$ 个、一边 0 个）。递归深度变 $n$ ，每层划分 $\Theta(n)$ ，总共 $\Theta(n^2)$ 。比如输入已经有序、又总取最后一个元素做基准，就是这种最坏。

最好情况：每次基准恰好是中位数，完美对半切。递归深度 $\log n$ ，总代价 $\Theta(n\log n)$ ，和归并排序一样。

平均情况： $\Theta(n\log n)$ 。证明要点是——即使划分不是完美对半，只要期望上比较均衡（比如 1:9 甚至 1:99），递归树的高度仍是 $O(\log n)$ ，总代价仍是 $\Theta(n\log n)$ 。4.4 节的概率分析会给严格证明。

这里有个反直觉的事实值得记住：快排最坏是 $O(n^2)$ ，比归并的 $O(n\log n)$ 差；但实际工程几乎都选快排而不选归并。 原因有三：快排原地（归并要 $O(n)$ 额外空间）、常数小（划分是顺序访问，缓存友好，归并要拷来拷去）、平均真的很快。最坏 $O(n^2)$ 可以靠下面的随机化规避。

4.随机化快排：把最坏情况变成小概率事件

最坏情况之所以可怕，是因为"输入已序"这种触发条件在真实数据里太常见了。解决招数很巧：与其固定取最后一个元素，不如随机选一个做基准。 这样"最坏"不再由输入决定，而是由随机数决定——而随机出最坏划分的概率，随 $n$ 增大呈指数衰减。

RANDOMIZED-PARTITION(A, p, r)
    i = RANDOM(p, r)         // 随机挑一个
    swap(A[r], A[i])         // 换到末尾
    return PARTITION(A, p, r) // 走原来的划分

这一招把"输入决定的最坏"变成了"随机决定的、概率极小的最坏"。期望复杂度稳定在 $\Theta(n\log n)$ ，而且不依赖任何输入分布的假设——这是随机化算法的招牌优势：用随机性换鲁棒性。第六卷会系统地讲随机化，这里你先见识它的威力。

5.和归并排序的对照：分治的两种姿势

把两者摆一起，分治的两种典型形态一目了然：

	归并排序	快速排序
"分"	机械对半切（不看元素大小）	按基准划分（重头戏）
"合"	归并 $\Theta(n)$ （重头戏）	不用合（划分时已就位）
额外空间	$O(n)$	$O(1)$ 原地
最坏时间	$\Theta(n\log n)$	$\Theta(n^2)$
稳定	是	否

看出门道了没？分治算法的开销，要么重在"分"要么重在"合"。 归并把难活留给了合，快排把难活留给了分。这个"分/合哪个贵"的权衡，是设计任何分治算法都要想清楚的——第二卷结尾的 2.7 会把这个总结成设计法则。

6.练习

Q1. 对数组 [3, 8, 2, 5, 1, 4, 7, 6]，以最后一个元素 6 为基准做一次 PARTITION，写出划分后的数组和基准的最终位置。

扫描后，比 6 小的 3,2,5,1,4 挤到左段，大的 8,7 到右段，基准 6 放中间。划分后一种可能形态是 [3,2,5,1,4,6,8,7]，基准 6 在第 6 个位置（下标 6）。具体左段内部顺序取决于实现，关键是 6 左边全 $\le 6$ 、右边全 $>6$ 。

Q2. 快排最坏 $O(n^2)$ 什么时候出现？随机化快排为什么能避免？

最坏出现在划分极度不均——每次基准都是当前段的极值，导致一边空、另一边 $n-1$ ，递归深度退化成 $n$ 。固定取末尾元素时，"输入已序"这种常见数据就会触发最坏。随机化快排随机选基准，使"触发最坏"由输入属性变成随机事件，而随机出连续最坏划分的概率随 $n$ 指数衰减，于是期望复杂度稳定在 $\Theta(n\log n)$ ，不再受输入分布影响。

Q3.（思考题） 快排最坏 $O(n^2)$ 比归并的 $O(n\log n)$ 差，为什么工程里反而更爱用快排？

三点：快排原地（归并要 $O(n)$ 额外空间）；快排划分是顺序扫描、缓存友好、常数小（归并要反复拷贝，常数大）；随机化后快排的期望 $O(n\log n)$ 在实际数据上几乎总能达到，最坏几乎不出现。渐进复杂度看的是最坏/平均，但工程选型还要看空间、缓存、常数——快排在这些维度上全面占优。这正是 1.8 节强调"别只看渐进阶"的体现。

7.小结

快速排序用"按基准划分"这个重头戏的分治姿态，实现了原地、平均 $O(n\log n)$ 的排序。它的精髓是划分让基准归位、递归处理两侧、无需合并。最坏 $O(n^2)$ 的软肋被随机化选基准巧妙化解。下一篇我们把"划分"这个思想推到极致——不用排序，光靠划分就能在 $O(n)$ 里选出第 $k$ 小的元素。