快速选择(Quickselect)

定义

快速选择(Quickselect)由 Tony Hoare 提出(亦称 Hoare 选择算法),用于在无序数组中找出第 k 小(或第 k 大)的元素,而不必对整个数组排序。

原理

借用快速排序的分区(partition)操作:选一个主元把数组分成小于和大于两部分,根据主元最终位置与 k 的关系,只递归进入包含目标的一侧。平均时间复杂度 O(n),最坏 O(n²);采用随机化主元可使最坏情况以极低概率出现,而 Blum 等人提出的中位数的中位数(BFPRT)算法可保证最坏 O(n)。

应用

求中位数与任意分位数、Top-K 问题(如推荐系统取前 K 个候选)、统计截断,以及 C++ 标准库 std::nth_element 的典型实现基础。

优缺点

比完整排序省去无关部分的工作,常数小、原地进行;缺点是结果只保证第 k 位正确及两侧粗略划分,且非稳定操作。