Quick Select 快速选择

Apr 7, 2026

核心任务:

Top-K问题: 在一个数组中找第k小/大的元素

step1: 随机选择一个pivot

step2: 将数组分为3部分 $O(n)$

[ 小于 pivot ] pivot [ 大于 pivot ]

step3: 确定pivot的rank $O(1)$

k = rank(pivot)

step4: 递归查找

if i == k:
	return pivot
elif i < k:
	go to [ 小于 pivot ]
elif i > k:
	go to [ 大于 pivot]

p.s. step2 和 step3 可以看作一个step, 因为本质上都是同一次遍历数组后得到的结果.

$T(n)=T(n/2)+O(n)=O(n)$

每次选到最大或最小值 $T(n)=O(n^2)$

在绝大多数情况十分高效, 时间复杂度仅为 $O(n)$

在极端情况, 效率甚至低于排序, 时间复杂度达到 $O(n^2)$