算法与数据结构 · 第 4 课

Quickselect:为什么不排序就能找到第 k 小?

2026 年 10 月 23 日|第一周|约 18 分钟

归档说明: 本讲是依照当天课程主题重构的完整教材版,并非历史对话逐字恢复。四级题目和标准答案分开保存。

本课目标

亲手执行原地 Partition,理解其循环不变量;证明选择算法只需要递归目标所在一侧;从随机枢轴的好坏划分推导期望线性时间;理解确定性 BFPRT 为什么能做到最坏线性复杂度。

一、排序的任务比选择更强

把 n 个不同元素完全排序,需要确定所有元素的排列;上一讲证明比较排序最坏 Ω(nlogn)。但如果只想找第 k 小,问题要求的输出更少:只需判断有哪些元素排在第 k 个位置之前,不必知道它们彼此之间的顺序。

核心直觉:找一个枢轴 p,通过一次扫描把数组分成“小于 p、等于 p、大于 p”的三部分,就能知道等于 p 的一段在有序结果中的排名区间。如果 k 在其左侧,只继续搜索左侧;若 k 在右侧,只继续搜索右侧。

因此,Quickselect 与 Quicksort 的关键区别是:Quicksort 要把两边都排好;Quickselect 只进入与目标相关的一边。

二、先讲清楚 Partition 的循环不变量

在没有重复键时可使用 Lomuto Partition:选数组末尾元素 p 为枢轴,i 指向已处理、满足 ≤p 前缀的末尾之后位置。扫描指针 j 逐个访问最后一个元素之前的数据:

partition(A,l,r):
    p = A[r]; i = l
    for j from l to r-1:
        if A[j] <= p:
            swap(A[i],A[j]); i += 1
    swap(A[i],A[r])
    return i

每次循环开始时不变量是:

  • $A[l..i-1]\le p$,即已归类为较小元素的前缀;
  • $A[i..j-1]>p$,即已归类为较大元素的中段;
  • $A[j..r-1]$ 尚未扫描;$A[r]=p$ 始终作为枢轴。

若当前 $A[j]\le p$,把它交换到 i 处,使第一个区间长度加 1;否则保留在中间较大区域。循环结束后将枢轴交换至 i,得到 $A[l..i-1]\le p$、$A[i]=p$、$A[i+1..r]>p$,枢轴的最终下标被正确确定。

三、跟着图,一次一交换地执行

[[viz:quickselect]]

图中寻找第 4 小,最初取末尾的 7 为枢轴。完成分区后 7 的最终位置已经固定,且左侧各元素不要求有序。因为第 4 小不是 7,需要继续处理更小的一段。这里“左段长度”与“第 k 小的 k 是从1还是从0计”要清楚区分,防止 Off-by-one 错误。

独立数值例:输入 [5,1,4,2,6,3],枢轴为3。从左到右只将1与2收集至前缀,枢轴最终在零基索引2(第3小)。如果目标恰好是第3小,到这里就能直接返回枢轴,根本无需排序左右两段。

四、Quickselect 的正确性归纳

假设 Partition 不变量成立。返回的枢轴左侧元素均不大于它、右侧均严格大于它。在元素互异的情况下,枢轴排名 $r$ 唯一。如果 $k=r$,返回枢轴正确;若 $k<r$,正确目标一定属于左侧;若 $k>r$,属于右侧。下一步的区间严格变小。有限规模基例是只剩一个元素,它必然为目标。由递归归纳得到算法正确。

重复键需要修改:普通 Lomuto 使用 ≤p 时,全相等输入会把枢轴放到最右边,每次只丢弃一个位置。即使随机选枢轴,也没有平衡划分。可以使用 Dutch National Flag 三路分区,直接识别等于 pivot 的完整区间;如果 k 落在等值区间内即可返回,不继续递归。

五、为何期望 O(n),却不能保证每次 O(n)?

一次分区需要 Θ(n) 工作。若每次恰好丢掉最小元素,仍保留 n−1 个,递推 $T(n)=T(n-1)+cn=\Theta(n^2)$,这说明最坏情况确实可能平方。

随机化情况下(假定互异键并均匀随机选枢轴),枢轴的最终排名在 1 到 n 之间均匀。至少约一半的排名位于中间二分位范围内;出现这种“好枢轴”时,保留子问题规模不超过约 $3n/4$。坏枢轴也有可能,但它出现的概率会进入期望分析,不能把每轮都假定为好划分。

更精确的上界思路:令 $E[T(n)]$ 为最坏目标排名下、对算法内部随机性取期望的工作量。分区后只进入目标那侧,其规模不超过 $\max(j-1,n-j)$。于是

\[E[T(n)]\le cn+\frac1n\sum_{j=1}^{n}\max(E[T(j-1)],E[T(n-j)]).\]

使用归纳假设 $E[T(m)]\le a m$,括号中的最大问题尺寸平均约为 $3n/4$(较小 n 的常数边界可单独处理)。因此 $E[T(n)]\le cn+3an/4+O(a)$。选取足够大的 a 并吸收小规模误差,得到期望 $O(n)$。它不代表某次抽到一串坏枢轴时也只需线性工作。

六、BFPRT:最坏 O(n) 为什么可能?

确定性 Median of Medians(又称 BFPRT)的思路:

  1. 将 n 个元素划分为大小至多5的组,对每组用常数次比较求中位数。
  2. 在约 $n/5$ 个组中位数里递归找中位数,作为枢轴 p。
  3. 用线性时间 Partition,然后只搜索目标排名所在的那一侧。

为什么这个 p 足够好?至少一半组中位数不小于 p,而其中每一个完整的五元组至少有三个元素不小于该组中位数,所以至少约 $3n/10$ 个元素不小于 p;对小于 p 一侧同理。忽略有限个不完整组造成的 O(1) 误差,Partition 后最大保留部分至多 $7n/10+O(1)$。

因此最坏递推满足

\[T(n)\le T(\lceil n/5\rceil)+T(7n/10+O(1))+cn.\]

若归纳假设 $T(m)\le K m$,右端大约是 $(0.2+0.7)Kn+cn=0.9Kn+cn$。选取 $K\ge10c$ 并让有限小规模通过基例吸收误差,即可给出 $O(n)$ 上界。注意 BFPRT 的常数代价不一定在所有实际场景都比随机 Quickselect 更好。

七、空间和边界

原地 Partition 只需 $O(1)$ 辅助数组空间;若用递归形式,随机算法的栈深度会随划分而变化,坏序列可能到 O(n),可以改成 while 循环只修改左右边界,使额外栈为常数。三路分区是重复键频繁时的重要机制。

需要区分:随机化期望、确定性最坏、工作量 Work、真实硬件时间。相同的 O(n) 理论也可能因为比较、数据移动、缓存行为、常数因子而有明显运行时间差异。

八、下一讲

下一课回到势函数:为什么动态数组同时扩容和缩容时需要迟滞阈值,以及如何构造对所有操作序列有效的摊还界。

四级分级测评(100 分)

初次展示不含标准答案,前三题客观评分,Lv4 需人工/ChatGPT 或自评。

Lv1|核心机制|15 分|约 2 分钟

Quickselect 在一次正确的三路 Partition 后,为什么通常只需递归一个子区间?

A. 因为 Partition 已经把整个数组全局排序完毕

B. 因为枢轴左右的所有键分别小于与大于枢轴,目标排名只可能位于小于区、等于区或大于区之一

C. 因为两边都递归会违反比较排序下界

D. 因为随机枢轴保证每次都恰好按一半划分

可选提示:先写出 Partition 的不变量及枢轴的最终排名,再分析 k 落在哪一个区间。

Lv2|Partition 数值 Trace|20 分|约 4 分钟

使用 Lomuto Partition:最后一个元素为 pivot,以 <=pivot 的扫描规则从左至右比较并原地交换。输入 [9,2,7,4,1,8,3],首轮 Partition 结束后 pivot 的最终零基数组索引是多少?

可选提示:扫描前 6 个元素,把 <=3 的元素逐个交换到前缀,再与 pivot 交换。

Lv3|期望/最坏与重复键|25 分|约 5 分钟

关于 Quickselect 的最坏、期望复杂度和重复键处理,哪些判断正确?(多选)

A. 对于互异键、均匀随机枢轴,Quickselect 的期望比较总量为 O(n),但单次运行最坏可达 Θ(n²)

B. 若每次枢轴都是当前最小元素,目标恰好是最大元素,继续在 n−1 的一侧递归,总成本可达 Θ(n²)

C. Median-of-Medians(BFPRT)以适当的5元组分组和线性分区可实现最坏 O(n) 的选择算法

D. 面对全相等数组,使用 <=pivot 的普通双区间 Lomuto Partition 和随机枢轴仍必定只需 O(n) 总工作

可选提示:注意重复值下只按<=分区与真正的三路分区不同;期望与最坏也是不同保证。

Lv4|不变量与复杂度证明|40 分|约 12 分钟

A(10分)设计允许重复键的 Quickselect 三路 Partition,写出循环不变量并证明返回的第 k 小正确。B(12分)假设所有键互异且每步均匀随机选择枢轴,建立期望时间上界并解释为什么它是 O(n),而最坏仍可能 Θ(n²)。C(12分)解释 BFPRT 5 元分组、中位数的中位数为何确保至少约 3n/10 的元素被淘汰;写出 T(n)≤T(n/5)+T(7n/10+O(1))+O(n) 并证明 O(n)。D(6分)说明原地实现的额外空间与递归栈深度,以及全相等输入应如何处理。

可选提示:对 A 可维护 <、=、未知、> 四段。对 B 平衡枢轴有常数概率,或对全部排名平均最长子问题。对 C 别忘分组选中数目和剩余一侧的上界。