问题

介绍

选择问题(selection problem)是指: 在集合 $S$ 中查找第 $k$ 个最大（或最小）的元素.

基于快速排序算法的快速选择(quickselect)的基本步骤如下:

(1) 如果 $|S|=1$, 那么 $k=1$, 并将 $S$ 中的元素作为结果返回. 如果正在使用小数组的截止方法, 并且 $|S|\leq CUTOFF$, 则将 $S$ 排序并返回第 $k$ 个最小元.

(2) 选取一个枢纽元 $v\in S$.

(3) 将集合 $S-\{v\}$ 分割成 $S_1$ 和 $S_2$, 就像快速排序中所做的那样.

(4)

• 如果 $k\leq |S_1|$, 那么第 $k$ 个最小元必然在 $S_1$ 中. 在这种情况下, 返回 quickselect($S_1,k$).
• 如果 $k=1+|S_1|$, 那么枢纽元就是第 $k$ 个最小元;
• 否则, 第 $k$ 个最小元就在 $S_2$ 中, 它是 $S_2$ 中的第 $(k-|S_1|-1)$ 个最小元. 我们进行一次递归调用并返回 quickselect($S_2,k-|S_1|-1$).

与快速排序对比, 快速选择只进行了一次递归调用而不是两次.
快速选择的最坏情形和快速排序相同, 也是 $O(N^2)$.
直观开来, 这是因为快速排序的最坏情形发生在 $S_1$ 和 $S_2$ 有一个是空的时候; 于是, 快速选择也就不是真的节省一次递归调用.
 

但可以证明, 快速选择的平均运行时间是 $O(N)$. 具体分析类似于快速排序的分析.

References:

Mark Allen Weiss, 数据结构与算法分析 C++ 描述（第三版），张怀勇等译.  [P.213, $\S$7.7.6]