数据结构与算法 / 系统课时
确定性线性选择
确定性线性选择
随机化快速选择通常很快,但理论上仍可能连续遇到极差枢轴。确定性线性选择通过“五元素分组”和“中位数的中位数”选择枢轴,使每轮都能排除足够多的元素,从而把最坏时间复杂度保证为 。
学习目标
- 理解五元素分组如何构造质量可证明的枢轴。
- 能够实现支持重复元素的确定性选择算法。
- 能够根据递推关系解释最坏线性时间的来源。
枢轴构造与执行流程
算法先把当前序列按最多五个元素一组切分,对每组排序并取中位数,再递归选择这些中位数的中位数作为枢轴。随后按照“小于、等于、大于枢轴”分成三部分,只在包含目标下标的部分继续递归。

选择五个元素一组并不是随意规定。设组数 ,偶数组数时取中间偏右的组中位数。两个方向至少各有 个组中位数符合不大于或不小于枢轴。每个完整组贡献至少三个符合方向的元素,最多扣掉一个不满五个元素的组。因此两个方向各至少有 个元素,保留的严格一侧至多为 。重复值也符合这个非严格计数,并可通过等值区间一次排除。
三路划分对重复值尤其重要。若目标落在“等于枢轴”的区间,算法可以立即返回,不会因大量重复元素而反复递归。
最坏线性时间为何成立
设处理 n 个元素的最坏时间为 T(n)。寻找各组中位数需要线性工作,递归寻找中位数的中位数处理约 n/5 个元素,主递归最多处理约 7n/10 个元素,因此可以写成:
这里用 T(n) 表示规模至多 n 的最坏成本,c 是本层线性工作的常数。两个递归规模相加至多 ,当 n≥140 时至多 。用 强归纳,取 并覆盖较小规模,代入得到 。这给出固定单位比较成本下的最坏线性上界。与随机化快速选择相比,这种保证不依赖输入排列或随机运气,但常数因子更大,工程中通常只在需要最坏情况保证时采用。
本例每层用线性额外空间保存分组和分区。两次递归依次执行,任一时刻只保留一条调用路径,较大规模下每层长度按固定比例缩小,因此峰值辅助空间为 O(n)。通过原地分区可以降低额外空间,但实现会明显复杂。
完整可运行示例
将下面代码保存为 deterministic_select_demo.py。参数 k 仍按从 1 开始计数。
from typing import List
def deterministic_select(values: List[int], k: int) -> int:
if type(k) is not int or not 1 <= k <= len(values):
raise ValueError("k 必须位于 1 到数组长度之间")
return select_by_index(values, k - 1)
def select_by_index(values: List[int], target: int) -> int:
if len(values) <= 5:
return sorted(values)[target]
groups = [values[index:index + 5] for index in range(0, len(values), 5)]
medians = [sorted(group)[len(group) // 2] for group in groups]
pivot = select_by_index(medians, len(medians) // 2)
lower = [value for value in values if value < pivot]
equal = [value for value in values if value == pivot]
higher = [value for value in values if value > pivot]
if target < len(lower):
return select_by_index(lower, target)
equal_end = len(lower) + len(equal)
if target < equal_end:
return pivot
return select_by_index(higher, target - equal_end)
def main() -> None:
numbers = [12, 3, 5, 7, 4, 19, 26, 1, 8, 15, 11, 2, 10, 6, 9]
for k in (1, 8, 15):
result = deterministic_select(numbers, k)
print(f"第 {k} 小元素: {result}")
if __name__ == "__main__":
main()运行命令如下:
python deterministic_select_demo.py预期输出
第 1 小元素: 1
第 8 小元素: 8
第 15 小元素: 26常见错误与练习
常见错误是直接把每组中位数的普通平均值当作枢轴。算法需要的是“中位数集合中的中位数”,必须递归执行选择,而不是计算算术平均数。最后一个不足五个元素的组仍可参加代码中的枢轴选择。推导每个完整组贡献三个元素时,应将这个组扣除。
练习一:为函数加入比较次数统计,并与上一课的随机化快速选择在相同输入上比较。验收条件是两种算法都返回相同答案,并分别输出比较次数。
练习二:构造包含大量重复值的数组,验证三路划分能够直接覆盖目标位置。验收条件是查询最小值、中位位置和最大值时均返回正确结果。
本课总结
- 五元素分组让枢轴两侧都能排除可证明数量的元素。
- 递推式中两个递归规模比例之和小于
1,因此最坏时间为 。 - 三路划分可正确处理重复值,但当前实现以 额外空间换取清晰性。
下一课预告
完成线性选择后,下一阶段将把分区、顺序统计量与查找方法结合起来,进一步比较不同输入条件下的算法选择与工程权衡。