第 9 章 中位数与顺序统计量 (Medians and Order Statistics)
核心结论
-
顺序统计量 (Order Statistic)：第 \(i\) 小的元素。中位数是特例：奇数 \(n\) 时为第 \((n+1)/2\) 小；偶数时分下/上中位数，本书默认用下中位数（第 \(\lfloor (n+1)/2 \rfloor\) 小）。
-
最小/最大值：MINIMUM / MAXIMUM 算法用 \(n-1\) 次比较——这已是最优下界（每个非最小值至少输一次比较）。
-
同时找最小与最大：用「成对比较」只需 \(\lfloor 3n/2 \rfloor\) 次比较，比朴素的 \(2n-2\) 省 25%；下界也是 \(\lfloor 3n/2 \rfloor - 2\)（练习 9.1-2）。
-
期望线性选择 (RANDOMIZED-SELECT)：仿照快速排序的 PARTITION 但只递归一边；期望时间 \(\Theta(n)\)，最坏 \(\Theta(n^2)\)（连续选最差 pivot）。
-
最坏线性选择 (SELECT, 中位数之中位数算法)：分组（5 个一组）→ 求每组中位数 → 再求这些中位数的中位数作为 pivot → 划分递归；保证「每边至少去掉 30%」→ 最坏 \(\Theta(n)\)，但常数因子大。
-
算法选择权衡：期望线性 vs 最坏线性——实践中常用 RANDOMIZED-SELECT（实现简单、常数小）；SELECT 用于实时 / 安全场景（无最坏）。
|
本章主旨
本章解决「在 \(n\) 个元素中找第 \(i\) 小的元素」的问题。直接的解法是排序后取第 \(i\) 位，时间 \(O(n \lg n)\)——但对选择问题这是过度的，因为不需要全部顺序。本章给出三个更快的算法：(1) §9.1 极简情形（最小 / 最大 / 同时）；(2) §9.2 RANDOMIZED-SELECT（仿快速排序，期望线性）；(3) §9.3 SELECT（中位数之中位数，最坏线性，理论意义重大）。本章也是「分治」与「递归式（带单调性假设）」的精彩应用。 |
一、核心概念
本章围绕 5 个核心概念展开：从最小 / 最大这种极简情形引入「比较次数」的下界论证，再给出两种线性时间选择算法——一种期望线性（随机化）、一种最坏线性（确定性中位数之中位数）。
| 概念 | 定义 + 重要性 | 实现提示 |
|---|---|---|
顺序统计量与中位数 |
第 \(i\) 顺序统计量 = 第 \(i\) 小元素；中位数 = 第 \(\lfloor (n+1)/2 \rfloor\) 小（下中位数）。 |
§9.1；选择问题：输入是集合 \(A\) + 整数 \(i\)，输出是 \(A\) 中恰好有 \(i-1\) 个元素比它小的元素。 |
最小/最大比较下界 (n-1) |
任何算法确定最小值至少需要 \(n-1\) 次比较——每个非最小值必须输一次「淘汰赛」。 |
§9.1；MINIMUM 用 \(n-1\) 次；同理 MAXIMUM 用 \(n-1\) 次。 |
同时最小 + 最大 (\lfloor 3n/2 \rfloor) |
把元素两两配对比较 → 小者比当前最小、大者比当前最大；3 次比较处理 2 个元素。 |
§9.1；n 奇 vs 偶初始化细节不同；下界也是 \(\lfloor 3n/2 \rfloor - 2\)。 |
期望线性 RANDOMIZED-SELECT |
仿快速排序的 PARTITION，但只递归包含第 \(i\) 小的一边；期望 \(\Theta(n)\)，最坏 \(\Theta(n^2)\)。 |
§9.2；随机选 pivot 类似第 7 章；用 max(k-1, n-k) 上界 + 代入法证明期望线性。 |
中位数之中位数 SELECT (中位五) |
分组（5 个一组）→ 求每组中位数 → 求这些中位数的中位数作为 pivot；保证每边至少去掉 30%。 |
§9.3；5 不是魔法数——7 也行（练习 9.3-1），3 不行（递归式不收缩）。 |
二、详细笔记
9.1 最小值、最大值与同时求解
What：在最简单情形下找顺序统计量——最小值（第 1 顺序统计量）、最大值（第 n 顺序统计量）、或两者同时。
Why：用极端情形热身 + 建立「比较次数下界」的论证模式（淘汰赛 / 候选集合计数）；同时给出实际中常用的「成对比较」优化技巧。
How：
-
MINIMUM 算法（§9.1）：
\[\begin{array}{rl} 1 & \min = A[1] \\ 2 & \textbf{for } i = 2 \textbf{ to } A.\text{length} \\ 3 & \quad \textbf{if } \min > A[i] \\ 4 & \quad\quad \min = A[i] \\ 5 & \textbf{return } \min \end{array}\]比较次数 = \(n-1\)（每次维护当前最小）。
-
下界论证（§9.1）：把算法执行看作「淘汰赛」——每次比较输者必不可能是最小；除赢家外每个元素必须输至少一次，故至少 \(n-1\) 次比较。
-
同时最小 + 最大（§9.1）：把元素两两配对。
-
先对每对做 1 次比较。
-
再比较小者与当前最小、大者与当前最大 → 3 次比较处理 2 个元素。
-
总比较次数 = \(\lfloor 3n/2 \rfloor\)（n 偶数：\(1 + 3(n-2)/2 = 3n/2 - 2\)；n 奇数：\(3\lfloor n/2 \rfloor\)）。
-
比朴素的「分别求 min 和 max 用 \(2n-2\) 次」省约 25%。
-
When：
-
求一个最小 / 最大 → MINIMUM/MAXIMUM（\(n-1\) 次）。
-
同时求两个 → 成对比较（\(\lfloor 3n/2 \rfloor\) 次）。
-
「找次小元素」 → 锦标赛法：\(n + \lceil \lg n \rceil - 2\) 次比较（练习 9.1-1）。
Example：成对比较在 n = 8 个元素的例子：
* 配对：(4, 2) → 2, (7, 3) → 3, (9, 1) → 1, (6, 5) → 5。
* 当前最小候选 = ⟨2, 3, 1, 5⟩；当前最大候选 = ⟨4, 7, 9, 6⟩。
* 分别求最小（用 3 次）和最大（用 3 次），外加 4 次配对 → 总 \(3 + 3 + 4 = 10 = 3 \cdot 8 / 2 - 2\)。
9.2 期望线性时间选择 (RANDOMIZED-SELECT)
What：仿照 RANDOMIZED-QUICKSORT，用 RANDOMIZED-PARTITION 划分输入；但与快速排序不同的是，只递归包含第 \(i\) 小元素的那一边，另一边丢弃。
Why：选择问题不需要排序——只关心一个元素。这丢弃另一半的「信息」换取效率。期望 \(\Theta(n)\)，因为每次递归至少把问题规模砍掉一半（期望）。
How：
-
伪代码（RANDOMIZED-SELECT, §9.2）：
\[\begin{array}{rl} 1 & \textbf{if } p == r \\ 2 & \quad \textbf{return } A[p] \\ 3 & q = \text{RANDOMIZED-PARTITION}(A, p, r) \\ 4 & k = q - p + 1 \\ 5 & \textbf{if } i == k \quad \text{// pivot 是答案} \\ 6 & \quad \textbf{return } A[q] \\ 7 & \textbf{elseif } i < k \\ 8 & \quad \textbf{return } \text{RANDOMIZED-SELECT}(A, p, q-1, i) \\ 9 & \textbf{else } \textbf{return } \text{RANDOMIZED-SELECT}(A, q+1, r, i-k) \end{array}\]关键点：
-
第 4 行：k = 「pivot 在 A[p..r] 中是第几小」。
-
第 8 行：第 i 小在低侧 → 递归找低侧的第 i 小。
-
第 9 行：第 i 小在高侧 → 递归找高侧的第 (i-k) 小（因为已有 k 个元素被「跳过」）。
-
-
期望分析（§9.2）：
-
设指示变量 \(X_k = I\{递归调用时低侧有 k 个元素\}\)，\(E[X_k\) = 1/n]。
-
假设递归调用总在较大侧（这是上界），递归式：
\[E[T(n)] \leq \frac{2}{n} \sum_{k=\lfloor n/2 \rfloor}^{n-1} E[T(k)] + O(n)\] -
代入法证明 \(E[T(n)\) \leq cn]：代入后需要 \(-cn/4 + c/2 + an \geq 0\)，即 \(n \geq 2c/(c/4 - a)\)，对足够大 \(n\) 成立。
-
-
最坏情形 \(\Theta(n^2)\)：每次都选最差 pivot（最大或最小）→ 递归式 \(T(n) = T(n-1) + \Theta(n)\) → 求和得 \(\Theta(n^2)\)。
When：
-
「实现简单 + 实践中足够快」 → 用 RANDOMIZED-SELECT；实践中常数因子比 SELECT 小。
-
「无最坏性能保证就不可接受」（实时系统、安全关键） → 用 SELECT (§9.3)。
-
「需要找附近元素」（如排序后取子集）→ RANDOMIZED-SELECT 配合 PARTITION 一次定位。
Example：在 A = ⟨3, 2, 9, 0, 7, 5, 4, 8, 6, 1⟩ 上找第 5 小（期望）： * Pivot = 某随机元素；假设首次 Partition 得低侧大小 k = 5，则 pivot 恰是第 5 小——直接返回。 * 若 k = 6（pivot 是第 6 小），则找高侧的第 (5 - 6) < 0？—— 不会发生（练习 9.2-1 证明不会出现递归到大小 0 的数组）。
9.3 最坏线性时间选择 (SELECT)
What：确定性、分治的「中位数之中位数」算法——保证每次划分至少砍掉 30% 的元素，从而得到最坏 \(\Theta(n)\) 时间。
Why：第 8 章证明排序下界 \(\Omega(n \lg n)\)；但选择问题下界是 \(\Omega(n)\)（因为排序能解决选择但不是反之）——理论上能达到下界。本节给出达到下界的算法，理论意义重大。
How：
-
算法步骤（SELECT, §9.3）：
-
分 5 个一组：\(\lceil n/5 \rceil\) 组，每组 5 个，至多一组 less than 5。
-
组内中位数：用插入排序对每组排序（O(1) 时间），取中位数；得 \(\lceil n/5 \rceil\) 个中位数。
-
递归求中位数的中位数 x：用 SELECT 自身求这些中位数的中位数。
-
用 x 划分原数组：得低侧（\(< x\)）和高侧（\(> x\)），元素数分别为 \(k - 1\) 和 \(n - k\)（x 是第 k 小）。
-
递归或返回：若 i = k 返回 x；若 i < k 对低侧递归；若 i > k 对高侧递归找第 \(i - k\) 小。
-
最坏情况分析（§9.3）：
-
关键引理（§9.3，图 9.1）：至少 \(3n/10 - 6\) 个元素大于 x，至少 \(3n/10 - 6\) 个元素小于 x。
-
直观：5 个一组的中位数里，至少一半 ≥ x（除含 x 自身和最后一组）；这一半所在的整组中，至少 3 个元素严格 > x。
-
故递归式：
\[T(n) \leq \begin{cases} O(1) & \text{if } n < 140 \\ T(\lceil n/5 \rceil) + T(7n/10 + 6) + O(n) & \text{if } n \geq 140 \end{cases}\] -
代入 \(T(n) \leq cn\)，得 \(cn/5 + 7cn/10 + 7c + an \leq cn\)（需 \(c \geq 20a\)、\(n \geq 140\) 即可）。
-
-
练习 9.3-1（分组大小的影响）：
-
分组 7：每组中位数 ≥/≤ 中位数之中位数的元素数至少 4 个（\(4n/14 - 4\) 个），递归式 \(T(n/7) + T(5n/7 + ...) + O(n)\) → 仍线性（系数 \(1/7 + 5/7 < 1\)）。
-
分组 3：每组中位数 ≥/≤ 中位数之中位数的元素数仅 2 个（\(2n/6 - 2\) 个），递归式 \(T(n/3) + T(2n/3 + ...) + O(n)\) → 不能保证线性（系数之和 ≥ 1）。
-
When：
-
「最坏线性」理论需要 → SELECT。
-
「实现简单 + 常数小」 → RANDOMIZED-SELECT（实践中更常用）。
-
SELECT 常数因子大，主要用于理论应用（如它们对外部选择也有用）。
Example：n = 15 时的 SELECT 分组（图 9.1）：3 组各 5 个；每组中位数 = 第 3 小；中位数之中位数 = 这 3 个中位数的中位数 = 第 2 小的中位数；用此 pivot 划分，至少 6 个元素被丢弃到任一边。
9.4 两种选择算法的对比与应用
What：把 RANDOMIZED-SELECT 与 SELECT 与直接排序比较——得出实践选择准则。
Why：选择实现时常常面临「RANDOMIZED-SELECT vs SELECT vs 先排序」的选择——理解三者差异可以做出明智决策。
How：对比矩阵：
| 算法 | 最坏时间 | 期望时间 | 实践考虑 |
|---|---|---|---|
先排序 + 取第 i 位 |
\(\Theta(n \lg n)\) |
\(\Theta(n \lg n)\) |
实现最简单；i 多时更值 |
RANDOMIZED-SELECT |
\(\Theta(n^2)\) |
\(\Theta(n)\) |
实践中常数小；攻击者可能构造最坏 |
SELECT |
\(\Theta(n)\) |
\(\Theta(n)\) |
常数大；用于实时 / 安全场景 |
堆（先建堆 + 删 i 次） |
\(\Theta(n)\) + i \(\Theta(\lg n)\) |
— |
适合「i 小」的「top-i」问题 |
应用场景：
-
「i 已知且不变化」 → SELECT 一次性定位 + PARTITION 得第 i 小附近所有元素。
-
「i 是 top-k」 → 堆或 quickselect 变体。
-
「多次不同 i」 → 排序（指数次查询摊销后仍便宜）。
-
「中位数（i = n/2）」 → SELECT 或 RANDOMIZED-SELECT；中位数在分治算法中常用于「保证平衡」（如 quicksort median-of-three）。
When：实际工程中 RANDOMIZED-SELECT 是默认选择；SELECT 用于教学 / 最坏有界场景。
Example：
-
找数组的中位数 → RANDOMIZED-SELECT（k = ⌊n/2⌋）。
-
找 k 个最接近中位数的元素（练习 9.3-7） → 先用 SELECT 找中位数，再用线性时间取 |A[i] - med| 最小的 k 个。
-
Top-10 from 1M docs → 建最大堆（O(n)）+ 10 次 EXTRACT-MAX（O(10 lg n)）——比排序快。
三、关键图表
|
本章无独立编号图表
本章核心图（图 9.1，SELECT 划分分析）以「5 个一组按列摆放、白色为中位数、箭头从大指向小」的视觉形式呈现——本笔记用文字 + 公式表述；原书图见 CLRS 第 4 版第 222 页。 |
|
核心公式对照表
|
四、思维导图
mindmap
root((第 9 章 中位数与顺序统计量))
基本概念
第i小
中位数
下上中位
最小最大
n-1比较
成对法
3n/2
RANDOMIZED
仿快速排序
单边递归
期望Θ(n)
最坏Θ(n²)
SELECT
5个一组
中位之中位
至少砍30%
最坏Θ(n)
对比
实现简单
常数因子
实时vs平均
排序+索引
应用
中位数分治
top-k
区间元素五、重点与易错点
-
「中位数 vs 平均数」的概念差异：中位数是「顺序统计量」，平均数是「数值平均」；本章明确处理中位数。
-
下/上中位数只对偶数 \(n\) 有差：本书默认「下中位数」= 第 \(\lfloor (n+1)/2 \rfloor\) 小；实现时可参数化。
-
MINIMUM 的比较下界 \(n-1\) 是紧的：MINIMUM 用 \(n-1\) 次比较，达下界——最优。
-
同时最小 + 最大不是 \(2(n-1)\) 而是 \(\lfloor 3n/2 \rfloor\)：常见错误是分开两次 MINIMUM/MAXIMUM。
-
成对比较的初始化要小心：\(n\) 偶时前两个元素先比 1 次定 min/max；\(n\) 奇时把第一个同时作为初始 min 和 max。
-
RANDOMIZED-SELECT 不能排序：它只找一个元素；但可结合 PARTITION 排序（问题 9-1c）——用 SELECT + PARTITION 排序期望 \(O(n \lg n)\)。
-
RANDOMIZED-SELECT 期望 \(\Theta(n)\) 但最坏 \(\Theta(n^2)\)：连续选最差 pivot 是罕见但理论可能——McIlroy 1999 证明可针对具体非随机化实现构造 O(n²) 输入（与第 7 章同模式）。
-
SELECT 的 5 不是魔法数——7 也行（练习 9.3-1）但常数更大；3 不行（递归式不收敛）。一般地，分组大小 = 奇数 \(g\) 时，递归式要求 \(1/g + (g-2)/(g+1) < 1\)，等号解为 \(g = 5\)。
-
SELECT 实际不常用：常数因子大——实践中 RANDOMIZED-SELECT 更受青睐，SELECT 主要是教学价值。
-
「只递归一边」是期望线性的关键：和 quicksort 不同，quicksort 递归两边 → \(\Theta(n \lg n)\)；只递归一边 → 期望线性。
-
代入法中「假设 \(T(n)\) 是单调递增」：选取 max(k-1, n-k) 而不是具体哪一边是上界分析技巧——便于求和且确保上界。
-
「145 元素时调用 SELECT 得中位数」：常数很大的现实意味着 SELECT 在小输入下用插入排序更划算（与 quicksort 优化同理）。
-
黑盒中位数 = 线性选择（练习 9.3-5）：若已知 O(n) 的中位数算法，可用 PARTITION 替换 RANDOMIZED-PARTITION，对外提供「线性选择」接口。
-
问题 9-1c（排序 + 索引 + 排序）：用 SELECT 找第 i 大 + PARTITION + 排序 i 个最大的 = \(\Theta(n + i \lg i)\)，比纯排序 \(O(n \lg n)\) 省。
-
「线性选择不与排序下界矛盾」：因为选择问题比排序弱——选择不需要输出序列的排列。本章是「上界匹配下界」的精彩演示。
补充：与其他章节的衔接
-
第 2 章：MINIMUM/MAXIMUM 体现「单循环 + 维护当前最值」的模式；与插入排序的内层循环同源。
-
第 7 章：RANDOMIZED-SELECT 直接借用 RANDOMIZED-PARTITION；两者的差异（双边 vs 单边递归）是关键设计决策。
-
第 8 章：本章是「不排序也能达到线性」的存在性证明，与第 8 章的「比较排序必须 \(\Omega(n \lg n)\)」形成对比。
-
第 13 章 (红黑树)：第 13 章的中位数化方法是「顺序统计树」(OS-tree)，由 §14.1 给出——本章 SELECT 是其前身思想。
-
第 23 章 (最小生成树)：Kruskal 与 Prim 都用「最小生成树边的中位数 / 优先级」优化；选择问题在此作为子程序。
-
第 27 章 (并行算法)：并行 SELECT 选择 pivot 时多线程加速；第 9 章只是开始。