第 7 章选择 — 只找第 k 小,不必全排序¶

这一章讲什么: 从 n 个元素里找出「排好序后第 k 个位置的值」, 但不真的排序。它在全书链条里的位置:第 6 章的直接续章—— 快排的划分机制在这里变成 quickselect,位图/计数排序在这里变成 O(n) 选择器; 本章的结论(选择可 O(n))反过来解释了为什么「找中位数」不该用排序。

1. 顶层全景¶

  问题:arr 排好序后第 k 个位置的值(k=0 最小,k=n/2 中位,k=n−1 最大)
      │
      ├─ 键受限时(数字、范围小):不比较
      │    位图选择:无重复,O(n),重复即抛错
      │    计数选择:允许重复,累计计数过 k 即停
      │
      └─ 通用键:比较类
           部分选择排序 O(k·n):k 小好用;找中位数退化 O(n²)
           quickselect 家族 O(n) 平均:
             ├─ 随机 pivot(最坏 O(n²))
             ├─ median of medians(五元分组,保证 O(n))
             └─ repeated step(三元 ninther 两轮,快而仍 O(n))
           lazy select:随机采样定上下界 d/u,夹缝集合排序取中位
                        失败概率 O(n^(−1/4)),失败重试

  图说:先问键受限吗,再问 k 靠哪头,最后才在 quickselect 家族里挑 pivot 策略。

2. 主线例子:同一数组找第 6 小,三种走法¶

用原书图 7-3 的数组演示(数取自原书插图,值为 [22, 9, 60, 12, 4, 56, 14, 34…], 位置按 1 起数描述,算法内部按 0 起数):

走法 A:位图选择(键受限版)。 建位图、找到第 6 个置位的位即答案——O(n), 但要无重复数字、范围小¹。

走法 B:部分选择排序(通用钥匙的笨办法)。 选择排序只跑 k 趟: 每趟找剩余最小值换到前面。跑 6 趟后第 6 个位置就是答案; 代价 O(k·n),k 接近 n/2(找中位)时就是 O(n²)³。

走法 C:quickselect(本章主角)。 随机取 pivot(比如 14),一趟划分后 pivot 落在第 4 位;要找第 6 位,只递归右侧;右侧取 56 为 pivot,划分后 56 在第 7 位, 超了,转左侧;取 22 为 pivot,落在第 5 位,再转右侧——单元素 34,它就是第 6 位。 注意左侧不有序、右侧不有序,只有「34 左边都 ≤34、右边都 ≥34」这个划分性质 ——这正是「选择不必排序」的全部根据⁴。

3. 核心原理¶

3.1 不比较选择:位图与计数的复用¶

位图选择就是位图排序的「提前退出版」:建图、扫描,数到第 k 个置位返回; 重复键直接抛错¹。计数选择允许重复:从左累计计数, 一旦累计超过 k,当前键就是答案——注意判断是 j > k(超过)而不是 j === k, 因为重复值会一次跳过多格²。两者都 O(n),但键受限, 通用场景还是得回到比较类。

3.2 quickselect:快排省掉一半递归¶

代码与快排的唯一差别在划分之后:快排递归两侧,quickselect 只递归包含 k 的那侧 (p === k 时直接收工)⁵。平均 O(n) 的直觉:pivot 落在中间时, 每次划掉一半,总工作量 n + n/2 + n/4 + … ≈ 2n——等比数列求和,线性。最坏仍是 O(n²)(每次 pivot 都取到最值),修复手段就是换 pivot 策略。

median of medians(保证 O(n)):五步——五元分组 → 各组中位数 → 中位数的中位数做 pivot。为什么稳?45 个元素的示意图里,pivot 不小于整组三分之一的元素、也不大于另外三分之一:每递归一层,问题规模至多缩到 2/3, 递推解出来是线性⁶。代价是常数大、代码长。

repeated step(实用折中):三元一组取中位(ninther 手法)做两轮, 问题缩到 1/9,再用递归求最终 pivot——「中位数的中位数的中位数」。同样可证 O(n),常数比五元版小得多⁷。

习题答案还有两个工程变体:尾递归改循环(消除递归开销)⁸、复制数组再划分(消除「改动输入」的副作用,第 2 章纯度纪律)⁹。

3.3 lazy select:用概率换简单¶

找中位数的另一个思路, radically 不同:不划分,采样¹⁰:

从 S 随机抽 n^(3/4) 个样本 R,排序(归并,样本小所以 O(n) 内);
在 R 里取 d = R[ sR/2 − √n ]、u = R[ sR/2 + √n ] 两个界;
统计 S 中小于 d 的数量 dSize、大于 u 的数量 uSize、夹在中间的集合 m;
三个健康检查:dSize ≤ n/2?uSize ≤ n/2?|m| ≤ 4n^(3/4)?任一不过就整个重来;
排序 m,取第 (n/2 − dSize) 个即中位数。

为什么敢这么干:随机样本的中位数大概率接近真中位数,±√n 的区间大概率罩住它; 失败概率是 O(n^(−1/4))——n=10,000 时约 10%,连跪三把的概率万分之一¹¹。这是全书第一次出现「允许偶尔失败、靠重试兜底」的算法,第 12 章的随机化 BST 和第 8 章的采样都建立在这个哲学上。

3.4 习题答案里的三个硬知识¶

锦标赛计数(7.1):111 人淘汰赛,每场淘汰一人,决出冠军要 110 场 = n−1; 找亚军不必再赛所有人——只可能是输给冠军的那几个人,最多再赛 ⌈log₂ n⌉ 场。即「两个最小值的总比较次数 n−1 + ⌈log n⌉」,这是选择下界的一个经典直觉¹²。
五元中位只需 6 次比较(7.2):先 a:b、c:d 比,跨组比一次淘汰一个候选, 再和 e 比两次收尾——medianOf5 代码直接可用,升级 simpleMedian¹³。
k 接近 n 的对称技巧(7.3):找第 k 大 = 找第 (n−k) 小; 数字键还可以全体取反找第 (n−k) 小再取反回来¹⁴。

4. 作者的判断与证据¶

「选择比排序快」由问题本身保证:只需 k 位信息,不必全序——本章全部算法都建立在这个观察上,且 JS 没有内置选择函数,「本章实现无法回避」¹⁵。
平均 O(n) 给了直觉,证明明说不给:「它们的性能证明往往复杂,故略去」; 唯一的完整保证是 median of medians 的 2/3 收缩论证⁶。
lazy select 的失败概率给的是大 O 而非数值:「证明高度依赖概率论证,此处不见」 ——读者拿到的是可用算法 + 可信度直觉,不是可验证的分析¹⁰。
pivot 策略的取舍有明确工程口径:随机版最简、五元版有保证、三元两轮版常数最优(习题 7.6 还给了免递归的「西西里版」并引了 Battiato 等人的论文)¹⁶。

判断(我们的,不是书里的): 本章的教学骨架其实是一条「对随机性的态度」递进:位图/计数(确定、受限)→ 随机 pivot quickselect(赌,可能输)→ median of medians(拒绝赌,用结构保证)→ repeated step(结构+少量随机)→ lazy select(全面拥抱随机+重试)。这条线在第 8 章(随机洗牌必须公平)、第 12 章(随机化 BST)和第 15 章(概率性摊还)会一再重现, 值得把它当成本章真正的主线。 如果错,会错在: 这条「态度线」是我们从编排顺序里读出来的, 书里并未明言;若作者只是按历史发展排序,这条解读就过度发挥了—— 但各节的选择确与这条线吻合。

5. 边界与局限¶

证明普遍缺席:quickselect 平均线性、mom 线性、repeated step 线性、 lazy select 失败率,全部「证明略」——要严谨论证得去算法分析教材。
中位数定义简化:本书的「中位数」就是第 n/2 位元素,不取偶数长度的两中值平均; 统计学的定义被一句 NOTE 带过了事¹⁷。
lazy select 的常数与边界条件(小数组、重复键)没讨论,直接搬用要小心。
选择下界 Ω(n) 只字未提(显然,每个元素至少看一眼)—— trivial 但被略过。

6. 可带走的¶

选择问题:k=0 最小、k=n−1 最大、k=n/2 中位;比排序弱,所以能快于 O(n log n)。
键受限(数字、小范围、看重复与否)先想位图/计数选择,O(n)。
部分选择排序 O(k·n):k 很小(k≤√n)时是实用默认;找中位别用它。
quickselect = 快排只走一半;pivot 落 k 位即收工;平均 O(n)、最坏 O(n²)。
pivot 三策略:随机(最简)、median of medians(五元分组,保证线性)、repeated step(三元两轮 ninther,常数小)。
lazy select:采样 n^(3/4) 定上下界、夹缝排序取中位;失败率 O(n^(−1/4)),重试兜底。
工程变体:尾递归化循环、复制输入消副作用。
两个硬事实:双最小时比较次数 n−1+⌈log n⌉(锦标赛);五元中位 6 次比较够。

7. 原文地图¶

主题	原书章	原文位置
问题定义(无需排序)	Selection Without Comparisons	`text/23-fm-selection-without-comparisons.txt:18`(搜「kth」)
位图/计数选择	Selection Without Comparisons	`text/23-fm-selection-without-comparisons.txt:62`(搜「bitmapSelect」) · `text/23-fm-selection-without-comparisons.txt:119`(搜「countingSelect」)
部分选择排序 O(kn)	Selection Without Comparisons	`text/23-fm-selection-without-comparisons.txt:154`(搜「sortingSelect」) · `text/23-fm-selection-without-comparisons.txt:172`(搜「middle element」)
quickselect 代码与走查	Selection Without Comparisons	`text/23-fm-selection-without-comparisons.txt:191`(搜「6th」) · `text/23-fm-selection-without-comparisons.txt:208`(搜「quickSelect」)
median of medians	Selection Without Comparisons	`text/23-fm-selection-without-comparisons.txt:260`(搜「five」) · `text/23-fm-selection-without-comparisons.txt:288`(搜「two-thirds」)
repeated step	Selection Without Comparisons	`text/23-fm-selection-without-comparisons.txt:362`(搜「one-ninth」)
lazy select	Selection Without Comparisons	`text/23-fm-selection-without-comparisons.txt:439`(搜「n3/4」) · `text/23-fm-selection-without-comparisons.txt:468`(搜「lazySelectMedian」)
习题 7.1–7.6	Chapter 7	`text/70-ch07-chapter-7.txt:7`(搜「110」) · `text/70-ch07-chapter-7.txt:16`(搜「medianOf5」) · `text/70-ch07-chapter-7.txt:89`(搜「while (left」)
西西里版(免递归 ninther)	Chapter 7	`text/70-ch07-chapter-7.txt:137`(搜「swapIfNeeded」)

出处:「Selection Without Comparisons」第 62–88 段(text/23-fm-selection-without-comparisons.txt:62,搜「bitmapSelect」)。原文:建位图同排序版,扫描时计数 j 到 k 返回该键;「显然 O(n)」;重复键抛错。 ↩↩
出处:「Selection Without Comparisons」第 119–136 段(text/23-fm-selection-without-comparisons.txt:119,搜「countingSelect」)。原文:j += count[...] 后「if (j > k) return i」;第 113 段提醒「累计和可能因重复值超过 k」。 ↩
出处:「Selection Without Comparisons」第 151–172 段(text/23-fm-selection-without-comparisons.txt:154,搜「sortingSelect」)。原文:选择排序循环只跑到 k;性能 O(kn),k=n/2 时 O(n²)。 ↩
出处:「Selection Without Comparisons」第 191 段(text/23-fm-selection-without-comparisons.txt:191,搜「6th」)。原文走查:pivot 14 落第 4 位 → 右侧;pivot 56 落第 7 位 → 左侧;pivot 22 落第 5 位 → 右侧单元素 34。「34 左边是较小值(不必有序),右边是较大值。」 ↩
出处:「Selection Without Comparisons」第 208–234 段(text/23-fm-selection-without-comparisons.txt:208,搜「quickSelect」)。原文:划分与快排相同;之后 if (p === k) return; else if (p > k) 递归左; else 递归右。 ↩
出处:「Selection Without Comparisons」第 260–288 段(text/23-fm-selection-without-comparisons.txt:260,搜「five」)。原文:五元分组、组中位、中位的中位做 pivot;「灰色值(45 个中的 15 个,三分之一)保证不大于 pivot」;最坏递归规模 2/3,「可证 O(n)」。 ↩↩
出处:「Selection Without Comparisons」第 354–418 段(text/23-fm-selection-without-comparisons.txt:362,搜「one-ninth」)。原文:三元取中两轮把数组缩到 1/9;「某种意义上你在选中位数的中位数的中位数」;同样可证 O(n)。 ↩
出处:「Chapter 7」第 88–114 段(text/70-ch07-chapter-7.txt:89,搜「while (left」)。答案原文:循环代替递归,p===k 时 left = right = k 退出。 ↩
出处:「Chapter 7」第 123–128 段(text/70-ch07-chapter-7.txt:124,搜「const copy」)。答案原文:const copy = [...arr]; quickSelect(copy, ...); return copy[k];。 ↩
出处:「Selection Without Comparisons」第 433–460 段(text/23-fm-selection-without-comparisons.txt:439,搜「n3/4」)。原文:样本 n^(3/4)、d/u 取排序样本 ±√n 位、三个失败检查、m[Math.floor(len/2) - dSize];「性能证明高度依赖概率论证,此处不见」。 ↩↩
出处:「Selection Without Comparisons」第 460 段(text/23-fm-selection-without-comparisons.txt:460,搜「10 percent」)。原文:失败概率 O(n^(−1/4));若失败率 10%,连败两次 1%,连败三次千分之一。 ↩
出处:「Chapter 7」第 7 段(text/70-ch07-chapter-7.txt:7,搜「110」)。答案原文:每场淘汰一人,冠军需 n−1 场;亚军只可能在冠军手下败过,最多再赛 ⌈log₂ n⌉ 场;总比较 n−1+log₂ n。 ↩
出处:「Chapter 7」第 16–41 段(text/70-ch07-chapter-7.txt:16,搜「medianOf5」)。答案原文:6 次比较的五元中位;逐步论证 a<b、c<d、a 被淘汰、b/c 较低者被淘汰、末步取 c/e 或 b/d 的较小者。 ↩
出处:「Chapter 7」第 76–79 段(text/70-ch07-chapter-7.txt:76,搜「going down」)。答案原文:k 接近 n 时改从尾部选最大;或与 n/2 比较选方向;数字键可全体取反找第 n−k 小再取反。 ↩
出处:「Selection Without Comparisons」第 516 段(text/23-fm-selection-without-comparisons.txt:516,搜「ready-made」)。原文:「选择问题不如排序常见,JS 不提供现成方法不足为奇——若需要这功能,本章实现无法回避。」 ↩
出处:「Chapter 7」第 134–196 段(text/70-ch07-chapter-7.txt:137,搜「swapIfNeeded」)。答案原文:循环版 ninther(西西里法),引 Battiato 等《An Efficient Algorithm for the Approximate Median Selection Problem》。 ↩
出处:「Selection Without Comparisons」第 32 段(text/23-fm-selection-without-comparisons.txt:32,搜「average」)。原文注释:统计学定义要偶数长度取两中值平均;「我们不这么做」,偶数长度需调两次选择算法再求均值。 ↩

第 7 章 选择 — 只找第 k 小,不必全排序¶