形式陈述

选择算法在未排序数组中找第 $k$ 小元素。Quickselect 以枢轴分区，只递归进入包含目标排名的一侧，随机枢轴给期望 $O(n)$ 时间但最坏 $O(n^2)$。Median-of-medians 把元素五个一组，递归选组中位数的中位数作枢轴，保证每次丢弃固定比例，递推 $T(n)\le T(n/5)+T(7n/10)+O(n)$，从而最坏 $O(n)$。原地实现通常只需常数额外数组空间加递归栈。

直觉

分区后，枢轴的最终排名已知。目标在左就完全忽略右边，在右就忽略左边，因此每层只保留一个子问题。

例子与边界

找中位数时，随机 Quickselect 在实践中常比保证线性的算法常数更小。若每次总选最小元素为枢轴，会退化为 $n+(n-1)+\cdots$。重复元素需要三向分区或仔细定义“等于枢轴”的排名区间，否则可能不收缩。线性选择不产生完全有序数组；若随后需要所有排名，排序仍更合适。比较模型下选择有 $\mathrm{\Omega }(n)$ 下界，因为至少要检查所有潜在极端元素。

推论与应用

选择算法用于中位数、top-k 阈值、线性时间分位数和鲁棒统计，并作为快速排序分区与确定性枢轴设计的基础。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。
• Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998，Chs. 5–6。