3.2 Selection、quickselect 与 linear-time sorting

选择问题只要求一个给定秩的元素，排序却要给出全部元素的完整次序。这个区别使 quickselect 可以舍弃不会影响目标秩的工作。Counting sort 与 LSD radix sort 更进一步：它们利用 key 的额外结构跨过比较排序的下界，但必须明确说明值域、位数与计算模型。

动机

假设一个 list 有数百万个值，而我们只需要中位数。先完整排序当然可以得到答案，可是完整次序包含的信息远多于一个中位数。选择算法之前，先确认题目究竟要求什么 output，是重要的算法设计习惯。

仓库中的 tutorial 依次给出三层思路。完整排序是容易理解的基线；partial selection sort 只放好最前面的若干 order statistics；quickselect 重用 quicksort 的 partition，但只进入可能含有目标的一边。随后，linear-time sorting 讲义改变计算模型：有界整数可以直接计数，多位 key 则可以逐位稳定排序。

本节处理的是静态、单次查询。若数据不更新而要查询很多个秩，先排序一次可能合理；若查询之间还会频繁插入和删除，dynamic selection tutorial 指向维护 subtree size 的高度平衡搜索树。它的对数保证依赖平衡性和 metadata 的正确维护，因此完整实现应放在 tree notes；这里仅说明静态选择与动态 order statistics 的边界。

定义

选择问题

给定含 $n$ 个 key 的 list $A$ ，以及满足 $1 \le k \le n$ 的整数 $k$ ，返回 第 $k$ 小的 key。秩采用 1-based，伪代码中的 array index 可以采用 0-based。重复值按出现次数分别计入：在 $[2,2,5]$ 中，第 1 小和第 2 小都是 $2$ 。

$k=1$ 与 $k=n$ 分别是 minimum 与 maximum，只需一次扫描，所以 comparison model 下的 selection 并不存在一般性的 $\Omega(n\log n)$ 下界。后文的下界针对输出完整次序的排序，而不是只找一个秩。

Partial selection sort 执行 selection sort 的前 $k$ 轮。第 $i$ 轮找出剩余 suffix 的最小值，与位置 $i$ 交换，最后返回 A[k - 1]；array 实现无需真的删除元素。比较次数恰为

\sum_{i=0}^{k-1}(n-i-1) =k(n-1)-\frac{k(k-1)}2,

所以是 $O(kn)$ 。固定常数 $k$ 时为线性；当 $k=\Theta(n)$ 时则为二次。

定义

Partition 契约

对长度为 $m$ 的当前 subarray，Partition 返回 index $p$ ，把 pivot 放在 A[p]，并保证 $p$ 左边每个 key 都不大于 A[p]，右边每个 key 都不小于 A[p]。因此即使有重复值，pivot value 也是局部第 $p+1$ 小的一个合法值。这个“pivot 最终 index”契约比只返回两个区域边界的 partition 更强。

若 $k$ 是相对于当前 subarray 的 1-based rank，正确分支结构是：

Quickselect(A, m, k):
    require 1 ≤ k ≤ m
    if m == 1: return A[0]
    p = Partition(A, m)          // p 是 pivot 最终的 0-based index
    if k - 1 == p: return A[p]
    if k - 1 is below p: return Quickselect(A[0:p], p, k)
    return Quickselect(A[p+1:m], m-p-1, k-p-1)

相等分支不可省略。进入右边时，新 rank 要减去左边的 $p$ 个位置和 pivot 本身。

每次 recursive call 开始时都保持这个 invariant：当前 subarray 含有原题所求的 order statistic，而参数 $k$ 是它在当前 subarray 内的 rank。左边 call 没有丢弃任何更小位置，所以保留 $k$ ；右边 call 恰好丢弃 $p+1$ 个位置，所以使用 $k-p-1$ 。Equality return 在 pivot 处停止，而且两个 recursive branches 都严格短于 parent，因此 base case 必会到达。若 partition 返回的是 Hoare-style boundary 而不是 pivot 最终 index，就需要另一套论证，不能原样代入这段 pseudocode。

Randomized three-way quickselect

上面的 source teaching trace 使用 two-way final-index partition。若 input 可能有 duplicates，而我们要证明 expected-time guarantee，应另用 three-way variant：从当前 records 中 uniform random 选一个 pivot，再分成 strict-less block $L$ 、equal block $E$ 与 strict-greater block $G$ 。令 $k$ 是 1-based local rank， $\ell=|L|$ 、 $e=|E|$ ：

RandomizedQuickselect(A, m, k):
    pivot = key of a uniformly random record in A
    (L, E, G) = ThreeWayPartition(A, pivot)
    if k ≤ |L|:       return RandomizedQuickselect(L, |L|, k)
    if k ≤ |L| + |E|: return pivot
    return RandomizedQuickselect(G, |G|, k-|L|-|E|)

这里保持同一个 recursive-call invariant，但 greater branch 丢弃的 prefix 大小变成 $\ell+e$ 。每次 recursive call 都只进入 strict block，所以规模严格缩小；若所有 keys 相等， $E$ 就是整个 input，algorithm 做一次 $\Theta(m)$ partition 后直接 return。这个 three-way contract 也不同于 Hoare boundary，必须按自身语义实现和证明。

定义

稳定排序

若具有相同 key 的 records 在 output 中保持 input 的相对次序，sorting routine 就是 stable。当后续 pass 按 compound key 的另一部分排序，并且必须保存早先 pass 建立的次序时，stability 是正确性条件。

定义

Counting sort

若整数 key 落在 inclusive range $0,1,\ldots,K$ ，标准 stable counting sort 需要 $K+1$ 个 counters。它先统计频率，再求 prefix counts，最后从右到左扫描 input，把 records 放进独立 output array。时间为 $\Theta(n+K)$ ；若同时计入 output 与 count arrays，auxiliary space 为 $\Theta(n+K)$ 。这个标准 stable 版本不是 in-place。

定义

LSD radix sort

设每个非负 key 在 base $b$ 下有 $d$ 位。Least-significant-digit (LSD) radix sort 先对 digit $0$ 做 stable sort，再处理 digit $1$ ，直到 digit $d-1$ 。若每一轮用 counting sort 处理 $b$ 种 digit value，总时间为 $\Theta(d(n+b))$ ，auxiliary space 为 $\Theta(n+b)$ 。

对于 $B$ -bit machine words，若每个 digit 取 $r$ bits，则 $d=\lceil B/r\rceil$ 、 $b=2^r$ ，所以成本为 $\Theta(\lceil B/r\rceil(n+2^r))$ 。较大的 digit 减少 passes，却扩大 counter array；较小的 digit 使用更紧凑的 counters，却要多次扫描 array。

因此“linear”是有条件的： $K=O(n)$ 时 counting sort 才是 $\Theta(n)$ ；若 representation 使 $d$ 为常数且 $b=O(n)$ ，LSD radix sort 才是 $\Theta(n)$ 。负数、变长表示或巨大 key universe 都需要额外处理，不能直接宣称无条件线性。

定理 / 命题

定理

Quickselect 为何不需要完整排序

假设 Partition 满足 pivot-final-index 契约。若返回 index $p$ ，局部第 $p+1$ 小就是 pivot；更小的目标 rank 在 left subarray；更大的目标 rank 在 right subarray，并调整为 $k-p-1$ 。因此每次 partition 后至多只需一次 recursive call。

定理

比较排序的 decision-tree 下界

对于由 $n$ 个互异 key 构成的任意 input，任何只通过 key comparison 获得相对次序的 deterministic sorting algorithm，都存在需要 $\Omega(n\log n)$ 次 comparisons 的 worst-case execution。若有界整数可以作为 array index，这个模型假设便不再适用。

定理

LSD radix sort 的正确性

完成 digit $0,1,\ldots,j$ 的 stable passes 后，array 按照由这 $j+1$ 个低位组成的 base- $b$ suffix 排好。处理全部 $d$ 位后，这个 suffix 就是完整 key，因此 array 完全有序。

证明思路

Quickselect 的分支正确性与成本

Partition 后，pivot 位于它在完整 sorted current subarray 中可以占据的最终位置；左边所有 key 不大于它，右边所有 key 不小于它。因此 target index 小于 $p$ 时不需要右边，大于 $p$ 时不需要左边，相等时立即 return。两边内部无须已经有序。

每次 partition 在长度 $m$ 的 subproblem 上花 $\Theta(m)$ 。若 pivot 每次都极端，size 依次为 $n,n-1,\ldots,1$ ，所以 $T(n)=T(n-1)+\Theta(n)=\Theta(n^2)$ 。若每次恰好缩半， $n+n/2+n/4+\cdots$ 的 geometric sum 只是线性成本的直觉，不能单独当作 average-case proof。

对 randomized three-way variant，明确假设每次从当前 subarray 中 uniform、independent 地选择一个 record，并且 comparison 与 swap 是 constant time。把相等 occurrences 任意赋予 sorted order 中连续的 ranks。所选 record 的 rank 落在中间一半的概率至少为 $1/2$ ；一旦发生，它的 strict-less 与 strict-greater blocks 都至多为 $3m/4$ 。目标要么在 equal block 直接 return，要么只在其中一个 strict block 继续。得到一次这种 constant-factor shrink 所需尝试次数期望至多为 2，每个 size scale 的 expected work 是 $O(m)$ 。对逐层缩小的 scales 求和得到 expected $O(n)$ ；第一次 partition 又给出 $\Omega(n)$ ，所以 expected time 为 $\Theta(n)$ 。 All-equal input 只需一次 linear pass；若 keys 互异而 pivots 每次都极端， worst case 仍为 $\Theta(n^2)$ 。

Decision-tree 下界证明

$n$ 个互异 arbitrary keys 有 $n!$ 种相对次序。Deterministic comparison sort 可以表示成 binary decision tree：internal node 是一次 comparison，leaf 必须识别一种 input permutation，所以正确算法至少需要 $n!$ 个 leaves。高度 $h$ 的 binary tree 最多有 $2^h$ 个 leaves，因此 $h\ge\log_2(n!)$ 。令 $q=\lfloor n/2\rfloor$ 。 $n!$ 中最大的 $q$ 个 factors 都至少为 $\lceil n/2\rceil$ ，所以

\log_2(n!)\ge \left\lfloor\frac n2\right\rfloor \log_2\!\left(\left\lceil\frac n2\right\rceil\right) =\Omega(n\log n).

于是至少一个 input 要走过这么长的 path。Counting sort 与 radix sort 使用 digit extraction、arithmetic 和 direct addressing，并限制 key representation，所以不违反这个只针对 comparison model 的结论。

LSD radix invariant

对 pass 数作 induction。Digit $0$ 排完后，array 按最低位有序。假设已经按 digits $0$ 至 $j-1$ 组成的 suffix 有序；下一次 stable pass 按 digit $j$ 排序。Current digit 不同的 records 由本轮直接排好；current digit 相同的 records 保持上一轮相对次序，因此仍按较低位 suffix 排好。于是处理 digit $j$ 后，array 按更长 suffix 有序。直到 digit $d-1$ ，suffix 等于完整 key。

例题详解

例题

Partial selection 的成本

对 tutorial array $[11,6,43,7,14,28,9,2,4,37,18,34,8]$ 找第 4 小，partial selection 依次把 $2,4,6,7$ 放到前四个位置。 $n=13,k=4$ 时，四次 suffix scan 共作 $12+11+10+9=42$ 次 comparisons，返回 A[3]=7。

完整 selection sort 要作 $78$ 次 comparisons；这里节省工作是因为 $k$ 小。若找 median， $k=\Theta(n)$ ，partial selection 仍为 quadratic。

例题

Quickselect partition trace

在 $[56,25,37,58,95,19,73,30]$ 中找第 2 小，并采用 tutorial 的 first-element pivot。

以 $56$ partition，得到 $[19,25,37,30,56,95,73,58]$ 。Pivot index 为 $4$ 、rank 为 $5$ ，所以只保留 left subarray $[19,25,37,30]$ 。
以 $19$ partition，pivot 局部 rank 为 $1$ 。目标在右边，新 rank 是 $2-1=1$ 。
在 $[25,37,30]$ 中，pivot $25$ 的局部 rank 为 $1$ ；相等分支 return $25$ 。

被舍弃部分不需要 sort。这个 trace 也说明 equality return 与 right-rank adjustment 缺一不可。

例题

Counting sort：从计数到 stable placement

令 $A=[0,5,3,2,3,0,5,1,5,2]$ 且 $K=5$ 。Keys $0$ 至 $5$ 的六个 counters 为

$C=[2,1,2,2,0,3].$

Prefix accumulation 后得到

$C'=[2,3,5,7,7,10],$

其中 $C'[i]$ 是不大于 $i$ 的 key 数。从右到左扫描 $A$ ，对 key $x$ 执行 B[--C'[x]] = record。例如最右的 $2$ 先把 counter $5$ 减为 $4$ ，再放到 zero-based index $4$ 。最终

$B=[0,0,1,2,2,3,3,5,5,5].$

若相同 key 带有不同 record identity，从右到左处理会让 input 中较后的 record 占据较后的 output position，从而保持相对次序。三阶段成本分别是 $\Theta(n)$ 、 $\Theta(K+1)$ 、 $\Theta(n)$ ，总计 $\Theta(n+K)$ 。

例题

Radix sort 为何需要 stability

对 $[329,457,657,839,436,720,355]$ 执行 base- $10$ LSD radix sort：

stable ones-digit pass： $[720,355,436,457,657,329,839]$ ；
stable tens-digit pass： $[720,329,436,839,355,457,657]$ ；
stable hundreds-digit pass： $[329,355,436,457,657,720,839]$ 。

以 tens pass 为例，tens digit 同为 $2$ 的 $720$ 与 $329$ 保持上一轮根据 ones digit 建立的次序。Unstable pass 可能把它们逆转，破坏 induction hypothesis。

常见错误

接受 $k=0$ 或 $k>n$ ，或混淆 1-based rank 与 0-based index。
把普通 partition boundary 当成 pivot 最终 index。
省略 quickselect 的 equality return，或进入右边时没有减去 $p+1$ 。
说 quickselect 永远 linear，没有 uniform randomized-pivot model 就把 balanced shrink 当成 average-case proof，或在允许 duplicates 时漏掉 three-way equal block。
写 sorting “至少是 $O(n\log n)$ ”。下界要写 $\Omega$ ，还要说明 arbitrary distinct inputs 与 comparison-only assumptions。
对 inclusive range $0,\ldots,K$ 只分配 $K$ 个 counters，或没有把全部 $K+1$ 个 counters 初始化为零。
把标准 stable counting sort 说成 in-place，或在递减 prefix position 时从左到右扫描 input。
对所有 radix-sort organization 作同一个 stability 声明；本节定理专指 whole-array LSD passes。

总结

Selection 只返回一个 order statistic；sorting 返回全部 rank information。
Partial selection 成本为 $O(kn)$ ，只在 $k$ 小时有吸引力。
Source two-way final-index trace 让 quickselect 只进入一边；duplicate-safe uniform randomized three-way variant 会在 equal block 直接 return，expected time 为 $\Theta(n)$ 。All-equal input 是 $\Theta(n)$ ，worst case 是 $\Theta(n^2)$ 。
Arbitrary distinct keys 的 comparison sorting 由 decision-tree proof 得到 worst-case $\Omega(n\log n)$ comparisons。
对 keys $0,\ldots,K$ ，stable counting sort 使用 $K+1$ 个 counters，时间 $\Theta(n+K)$ ，从右到左扫描以保证 stability；标准 output-array 版本不是 in-place。
含 $d$ 个 base- $b$ digits 的 LSD radix sort 用 stable digit passes，成本 $\Theta(d(n+b))$ ；是否线性取决于 representation parameters。

练习

思考检查

为什么 full sorting 比 selection 做更多工作？

比较题目要求的 output。

解答 · 答案

Selection 只要一个 ranked element；sorting 要知道所有元素的完整次序。