快速选择Quickselect

时间与空间#

n 为元素数；随机化分区选择第 k 小元素。

时间复杂度

期望 $O(n)$；最坏 $O(n^{2})$

辅助空间

原地迭代实现 $O(1)$

每次只继续进入包含目标秩的一侧。选择结果不代表两侧已经完整排序。Median-of-medians 等策略可给线性最坏界，但不是普通随机 quickselect 的保证。