第 7 章 快速排序 (Quicksort)
核心结论
-
快速排序 (Quicksort)：分治排序算法——选 pivot，把数组分为 ≤ pivot 和 > pivot 两部分，递归排序。最坏 Θ(n²)，期望 Θ(n lg n)，原地排序。
-
PARTITION 子程序 (Lomuto 版)：以 A[r] 为 pivot，把 A[p..r] 划分为 ≤ x 和 > x 两部分；Θ(n) 时间。
-
性能分析：最坏情况（每次划分极不平衡，如已排序输入）= Θ(n²)；最佳情况（每次均分）= Θ(n lg n)；平均 = Θ(n lg n)。
-
随机化版本 (RANDOMIZED-QUICKSORT)：在划分前先随机选 pivot；期望 Θ(n lg n) 对所有输入成立——任何输入都不会引发最坏情况。
-
指示随机变量分析 (引理 7.1)：期望比较次数 E[X] = Σ 2/(j-i+1) = O(n lg n)；两个元素被比较 ⟺ 它们所在区间中第一个被选为 pivot。
-
常数因子小：实践中常数因子比堆排序小约 2 倍——多数排序库默认选择快速排序。
|
本章主旨
本章是「分治思想 + 概率分析」的联合展示。快速排序以简洁著称（伪代码仅 7 行），但其性能分析比归并排序复杂——最坏 Θ(n²) 与期望 Θ(n lg n) 的巨大差异要求严格的概率分析。引入随机化后，最坏情况仅以「期望」出现（而非确定性的最坏）。本章也是「指示随机变量」技术的精彩应用。 |
一、核心概念
本章围绕 5 个核心概念展开：先描述快速排序与 PARTITION 子程序，再分析其最坏 / 最佳 / 平衡情况，然后引入随机化版本，最后用指示随机变量严格分析期望运行时间。
| 概念 | 定义 + 重要性 | 实现提示 |
|---|---|---|
快速排序 (Quicksort) 算法 |
分治：以 A[r] 为 pivot，划分 A[p..r] 为 ≤ pivot 与 > pivot 两部分，递归排序。 |
§7.1；QUICKSORT(A, p, r)；原地排序。 |
PARTITION (Lomuto 版) |
Θ(n) 子程序；以 A[r] 为 pivot；维护循环不变量「A[p..i] ≤ x，A[i+1..j-1] > x」。 |
§7.1；i = p-1 起始；j 从 p 到 r-1；最后交换 A[i+1] ↔ A[r]。 |
最坏情况分析 |
每次划分极不平衡（如 pivot 是最大/最小）→ 递归式 T(n) = T(n-1) + Θ(n) → Θ(n²)。 |
§7.4.1；输入已排序 / 逆序；T(n) = max_q (T(q) + T(n-q-1)) + Θ(n)。 |
随机化版本 (RANDOMIZED-QUICKSORT) |
PARTITION 前先 RANDOM(p, r) 选 pivot；期望 Θ(n lg n) 对任何输入成立。 |
§7.3；RANDOMIZED-PARTITION = 随机选 pivot + PARTITION。 |
期望分析 (引理 7.1) |
用指示随机变量 X_{ij} = I{z_i 与 z_j 比较}；E[X_{ij}] = 2/(j-i+1)；总 E[X] = O(n lg n)。 |
§7.4.2；两个元素被比较 ⟺ 它们所在区间中第一个被选为 pivot（指示变量法的精妙应用）。 |
二、详细笔记
7.1 快速排序与 PARTITION
What：QUICKSORT(A, p, r) 是分治排序：
-
Divide：调用 PARTITION(A, p, r) 得 q，使 A[p..q-1] ≤ A[q] ≤ A[q+1..r]。
-
Conquer：递归 QUICKSORT(A, p, q-1) 和 QUICKSORT(A, q+1, r)。
-
Combine：无需——原地排序。
PARTITION (Lomuto, §7.1)：
循环不变量：每次 j 迭代开始时：
-
A[p..i] ≤ x
-
A[i+1..j-1] > x
-
A[r] = x（pivot 未被移动）
Why：快速排序是「分治 + 原地 + 期望 O(n lg n)」的典范——实践中常数因子比堆排序小，比归并排序省空间（无需合并数组）。PARTITION 的设计巧妙：所有工作通过「单次扫描 + i 边界推进」完成。
How：正确性用循环不变量三步证明：
-
初始化：i = p-1, j = p → 两个区域都为空 → 不变量成立。
-
保持：分两种情况：A[j] > x（仅 j）或 A[j] ≤ x（i、交换 A[i] ↔ A[j]、j++）——两种情况都不变量都保持。
-
终止：j = r → 不变量覆盖整个数组，最后把 pivot 放到 i+1 位置。
When：实践中最常用的排序算法——C/C++ qsort、Java Arrays.sort(基本类型)、Python list.sort()、Unix sort 核心都基于快速排序（含各种优化）。
Example：图 7.1 —— PARTITION 在 A = ⟨2, 8, 7, 1, 3, 5, 6, 4⟩ 上：逐步把 ≤ 4 的元素移到左边，> 4 的元素移到右边，最后把 pivot 4 放到中间。
7.2 性能分析（最坏 / 最佳 / 平衡）
What：QUICKSORT 的性能取决于划分的「平衡程度」：
-
最坏划分：q = 0 或 q = n-1（pivot 是最大/最小）→ T(n) = T(n-1) + Θ(n) → Θ(n²)。
-
最佳划分：q = ⌊n/2⌋ → T(n) = 2T(n/2) + Θ(n) → Θ(n lg n)（主定理情形 2）。
-
常数比例划分（如 9:1）→ T(n) = T(9n/10) + T(n/10) + Θ(n) → 仍是 O(n lg n)。
Why：理解平衡对性能的影响——「常数比例的划分」（哪怕是 99:1）已足以保证 Θ(n lg n)；只有「极端不平衡」（每次都 0:n-1）才退化到 Θ(n²)。
How：图 7.4 —— 9:1 划分的递归树：每层总代价 cn，树高 ≈ log_{10/9} n = Θ(lg n)；总代价 O(n lg n)。
最坏情况的直觉（§7.2）：每次划分产生 0 元素和 n-1 元素子问题——递归式 T(n) = T(n-1) + Θ(n) 求和得 Θ(n²)。已排序输入触发最坏情况——实际中可在划分前「洗牌」或随机选 pivot 避免。
直觉：图 7.5 —— 即使「坏划分」紧跟「好划分」，总代价仍是 Θ(n)（因为好划分的 Θ(n) 吸收了坏划分的 Θ(n-1)）。
When：
-
关心最坏 → 用 RANDOMIZED-QUICKSORT 或尾部递归优化。
-
关心期望 → 任何 QUICKSORT 变体的期望都是 Θ(n lg n)。
-
实际中已排序 / 逆序输入常见——必须用 RANDOMIZED-QUICKSORT 或在划分前随机打乱。
Example：
-
A = ⟨1, 2, 3, 4, 5, 6, 7, 8⟩（已排序）：QUICKSORT 用 A[r] = 8 作 pivot → 划分 0:7 → 递归式 T(n) = T(n-1) + Θ(n) → Θ(n²)。
-
A = ⟨4, 1, 3, 2, 6, 5, 7, 8⟩：第一次划分 q ≈ 4 → 两半 ≈ 平衡 → Θ(n lg n)。
7.3 随机化版本 (RANDOMIZED-QUICKSORT)
What：RANDOMIZED-PARTITION 在 PARTITION 前先随机选 pivot；RANDOMIZED-QUICKSORT 用 RANDOMIZED-PARTITION 代替 PARTITION。
Why：保证「任何输入」都不会引发最坏情况——最坏情况仅以「概率 2^(-n)」出现（来自连续选最差 pivot 的罕见事件）。这是概率算法设计中「让输入无关」的经典案例。
How：RANDOMIZED-PARTITION（§7.3）：
关键：随机选 pivot 等价于「在划分前把数组随机打乱」——确保 pivot 均匀随机。
When：
-
任何「不能信任输入分布」的场景——通用排序库默认使用。
-
「最坏情况性能至关重要」的场景——如实时系统、安全相关代码（避免被精心构造的输入攻击，McIlroy 1999 证明非随机化快速排序可被 O(n²) 攻击）。
Example：RANDOMIZED-QUICKSORT 对已排序输入：第一次 pivot = 随机元素（期望中位数）→ 平衡划分 → 期望 Θ(n lg n)。McIlroy 的「杀手对手」可针对具体非随机化实现构造 O(n²) 输入——随机化版本免疫。
7.4 期望分析（引理 7.1 与式 7.4）
What：用指示随机变量严格证明 RANDOMIZED-QUICKSORT 期望比较次数 = O(n lg n)。
Why：引理 7.1 是「概率 + 算法分析」的精妙应用——把「比较次数」分解为「每对元素是否被比较」的指示变量之和，再用「区间中第一个被选为 pivot」的概率求期望。
How：分析步骤（§7.4.2）：
-
设排序元素为 z_1 < z_2 < … < z_n，定义 Z_{ij} = {z_i, …, z_j}。
-
关键观察：每对元素最多比较一次；z_i 与 z_j 被比较 ⟺ Z_{ij} 中第一个被选为 pivot 的是 z_i 或 z_j。
-
Z_{ij} 中每个元素等概率成为第一个 pivot：概率 1/(j-i+1)。
-
因此：
-
设 X = 总比较次数，X_{ij} = I{z_i 与 z_j 比较}，则 X = Σ X_{ij}，由线性期望：
-
令 k = j-i：
-
加上 O(n) 的 PARTITION 调用 → 期望运行时间 O(n lg n)。
When：当需要「严格证明随机算法的期望性能」时；展示指示变量方法的威力——避免直接枚举概率分布。
Example：z_3 与 z_7（i=3, j=7）：比较概率 = 2/(7-3+1) = 2/5；直觉：Z_{3,7} 有 5 个元素，每个等概率第一个被选为 pivot；只有 z_3 或 z_7 第一个被选时才发生比较 → 2/5。
7.5 性能对比与实践考量
What：把快速排序与其他 O(n lg n) 算法对比——快速排序通常是实践最优。
Why：理解「为什么快速排序」成为标准——不仅渐近最优，常数因子也小。
How：对比矩阵：
| 算法 | 最坏 | 期望 / 平均 | 原地 |
|---|---|---|---|
稳定性 |
实践常数 |
插入排序 |
Θ(n²) |
Θ(n²) |
是 |
是 |
小（n < 10） |
归并排序 |
Θ(n lg n) |
Θ(n lg n) |
否 |
是 |
中 |
堆排序 |
Θ(n lg n) |
Θ(n lg n) |
是 |
否 |
中大 |
快速排序 |
Θ(n²) |
Θ(n lg n) |
是 |
否 |
小 |
RANDOMIZED-QUICKSORT |
Θ(n²) (罕见) |
Θ(n lg n) |
是 |
否 |
小 |
常见优化（实践中）：
-
小数组用插入排序：当 n < ~10 时切换到插入排序（更小的常数）。
-
三数取中 (median-of-3)：pivot = median(A[lo], A[mid], A[hi])，避免已排序输入的最坏。
-
三路划分 (Dutch national flag)：处理重复键，把 == pivot 的单独成一段。
-
尾递归优化：先递归小数组，大数组用循环——栈深度 O(lg n)。
When：
-
默认排序 → 快速排序（实践中）。
-
需要稳定排序 → 归并排序。
-
最坏情况性能保证 → 堆排序。
-
数据接近有序 → Timsort（归并 + 插入混合，Python/Java 默认）。
-
重复键多 → 三路划分快速排序。
Example：Unix sort 默认用快速排序变体；C++ std::sort 用 introsort（快速 + 堆 + 插入混合，遇到深度过深时切换到堆排序保证最坏 O(n lg n)）；Python/Java 的 Timsort 是归并 + 插入混合，对部分有序输入极快。
三、关键图表
|
核心公式对照表
|
四、思维导图
mindmap
root((第 7 章 快速排序))
算法
分治
PARTITION
Lomuto
原地
划分
pivot=A[r]
i边界推进
不变量
性能
最坏Θ(n²)
最佳Θ(n lg n)
平衡划分
随机化
RANDOM(p,r)
避免最坏
期望Θ(n lg n)
期望分析
指示变量
X_ij
2/(j-i+1)
ln n
实践
插入小数组
三数取中
三路划分
尾递归
对比
归并稳定
堆最坏O(n lg n)
QUICKSORT实践最优五、重点与易错点
-
QUICKSORT 原地排序：与归并排序（需要 O(n) 辅助空间）相比，快速排序省空间——这是它在实践中常胜的关键之一。
-
Lomuto vs Hoare 划分：本书 PARTITION 是 Lomuto 版（用 A[r] 作 pivot）；原版 Hoare 划分（用 A[p]，双指针从两端靠拢）在某些场景更快（问题 7-1）。
-
最坏情况 Θ(n²) 不容忽视：已排序 / 逆序输入 + Lomuto PARTITION = 最坏——实际工程必须用 RANDOMIZED-QUICKSORT 或洗牌。
-
期望与最坏的差异：QUICKSORT 的「期望 Θ(n lg n) 但最坏 Θ(n²)」是算法的本质特征；这是 RANDOMIZED 版本的价值——把「最坏情况」的概率降至可忽略。
-
引理 7.1 的核心洞察：z_i 与 z_j 比较 ⟺ Z_{ij} 中第一个 pivot 是 z_i 或 z_j。这种「等价于第一个 pivot」的转换是分析的关键。
-
PARTITION 的循环不变量与 HEAPSORT 的循环不变量同源：都是「在某个区间上保持某种性质」——第 2 章循环不变量的思想贯穿全章。
-
「已排序输入是最坏」的直觉反例：直觉上「已排序」似乎应该是最佳——但对 Lomuto QUICKSORT 它是最坏，因为每次选最大/最小作 pivot。这是「为什么需要随机化」的最直观论据。
-
指示变量法不要求独立（第 5 章引理）：即使各 X_{ij} 之间相关（一个比较影响其他比较的可能性），线性期望仍然成立。
-
快速排序常数因子小：相比归并排序（每次需要合并）、堆排序（每次 MAX-HEAPIFY），快速排序的内层循环极简（比较 + 可能交换），所以常数小 ~2x。
-
「McIlroy 杀手对手」：针对具体非随机化实现可构造 O(n²) 输入；生产代码必须用 RANDOMIZED-QUICKSORT。
-
稳定性：QUICKSORT 不稳定——等价元素的相对顺序可能改变；归并排序稳定——选择时考虑此差异。
-
三路划分处理重复键：当有大量重复元素时，标准 QUICKSORT 退化为 O(n²)；三路划分（< / = / > 三段）处理得当，是 Java 7+ 对引用类型排序的默认。
-
尾递归优化降低栈深度：QUICKSORT 栈深度最坏 O(n)（连续最坏划分时）；改成「先小后大」递归 → 栈深度 O(lg n)。
-
本书 PARTITION 假设元素互异：分析中 Pr{z_i 与 z_j 比较} = 2/(j-i+1) 假设 z_i ≠ z_j；重复键情形单独处理（问题 7-2）。
-
快速排序是后续算法的基础：qsort 库、qselect（第 9 章顺序统计）、Strassen 等都用其思想。