第07章 快速排序 — 章节汇总

章节概览

本章系统介绍了快速排序（Quicksort）——实践中最常用的比较排序算法之一。快速排序由 Tony Hoare 于 1960 年发明，采用分治策略，通过分区（Partition）操作将数组划分为两个子数组，然后递归排序。尽管最坏情况运行时间为 $\Theta (n^2)$，但其期望运行时间为 $\Theta (n\lg n)$，且常数因子极小，加之原地排序和良好的缓存局部性，使其成为大多数标准库排序实现的首选。本章还介绍了随机化快速排序，通过随机选择枢轴（pivot）来避免最坏情况，并给出了期望运行时间的严格数学证明。

---

7.1~7.2 快速排序的描述与性能直觉

小节	核心主题	关键结论
7.1 快速排序的描述	QUICKSORT/PARTITION 伪代码与正确性	PARTITION 耗时 $\Theta (n)$；循环不变式证明正确性
7.2 快速排序的性能	最坏/最好/平衡分区分析	最坏 $\Theta (n^2)$；最好 $\Theta (n\lg n)$；平衡 $\Theta (n\lg n)$

核心思路：快速排序的分治三步为：分解（PARTITION 将数组以枢轴为界分为两部分）、解决（递归排序两个子数组）、合并（无需操作，因为分区已保证有序）。PARTITION 的循环不变式确保每次迭代后，枢轴左侧元素 $\le$ 枢轴 $\le$ 右侧元素。性能取决于分区的平衡程度——最坏情况（每次产生 0 和 n-1 的分区）退化为 $\Theta (n^2)$，而平衡分区（每次近似平分）达到 $\Theta (n\lg n)$。

---

7.3~7.4 随机化版本与严格分析

小节	核心主题	关键结论
7.3 快速排序的随机化版本	RANDOMIZED-PARTITION/QUICKSORT	随机选枢轴，期望性能不依赖输入
7.4 快速排序的分析	最坏 $\Theta (n^2)$ + 期望 $O(n\lg n)$ 严格证明	指示器随机变量方法，期望比较次数 $\le 2n\ln n$

核心思路：7.3 快速排序的随机化版本 通过在 PARTITION 前随机选择枢轴并交换到末尾，将算法的性能保证从”对特定输入分布的期望”转变为”对所有输入的期望”。7.4 快速排序的分析 给出了严格的数学证明：最坏情况使用代入法证明 $T(n)=\Theta (n^2)$；期望运行时间使用指示器随机变量（与5.2 指示器随机变量相同的技术），设 $X_{ij}$ 表示第 $i$ 小与第 $j$ 小元素是否被比较，通过分析比较发生的概率条件，得到期望比较次数 $\le 2n\ln n=O(n\lg n)$。

---

本章核心知识点

关键定义

概念	定义	出处
分区（Partition）	将数组以枢轴为界重排，使得左侧 $\le$ 枢轴 $\le$ 右侧	7.1 快速排序的描述
枢轴（Pivot）	PARTITION 选择的参考元素，CLRS 使用 $A[r]$	7.1 快速排序的描述
随机化分区	随机选择枢轴，使分区平衡性不依赖输入	7.3 快速排序的随机化版本

关键过程与复杂度

过程	功能	最坏时间	期望时间
PARTITION	以 $A[r]$ 为枢轴分区	$\Theta (n)$	$\Theta (n)$
RANDOMIZED-PARTITION	随机选枢轴后分区	$\Theta (n)$	$\Theta (n)$
QUICKSORT	确定性快速排序	$\Theta (n^2)$	取决于输入
RANDOMIZED-QUICKSORT	随机化快速排序	$\Theta (n^2)$	$O(n\lg n)$

核心定理

编号	内容	出处
定理 7.1	快速排序最坏情况运行时间为 $\Theta (n^2)$	7.4 快速排序的分析
定理 7.2	当所有元素互不相同时，RANDOMIZED-QUICKSORT 的期望比较次数 $\le 2n\ln n$	7.4 快速排序的分析
推论 7.1	RANDOMIZED-QUICKSORT 的期望运行时间为 $O(n\lg n)$	7.4 快速排序的分析

---

与前序章节的知识关联

前序章节	关联方式
第2章 入门	分治法（2.3节）是快速排序的设计基础；插入排序用于小分区优化
第4章 分治策略	代入法（4.3节）用于最坏情况证明；主定理用于最好/平衡情况分析
第5章 概率分析	指示器随机变量（5.2节）用于期望运行时间证明；随机化策略（5.3节）与 RANDOMIZED-PARTITION 对比
第6章 堆排序	堆排序 vs 快速排序的工程对比；Introsort 结合两者优势

---

学习路线

第7章学习路径：
  7.1 快速排序的描述（算法设计，建立直觉）
    → 7.2 快速排序的性能（性能直觉，四种场景分析）
      → 7.3 随机化版本（解决最坏情况问题）
        → 7.4 快速排序的分析（严格数学证明）

学习建议

本章是算法分析中”直觉先行、严格证明跟进”的典型范例。建议按 7.1 → 7.2 → 7.3 → 7.4 的顺序学习。7.1 的 PARTITION 循环不变式是理解快速排序的关键，务必彻底掌握。7.4 的期望运行时间证明是全书的数学分析高峰之一，需要扎实的第5章概率分析基础。如果对指示器随机变量不熟悉，建议先复习 5.2 指示器随机变量。

快速排序