Select 算法
I 编程珠玑(续)介绍的 Quickselect 算法
选择 N 个元素中的第 K 小(大)值，是日常场景中常见的问题，也是经典的算法问题.
选取 N 个元素的数组的中的第 K 小(大)值，最简单的想法是将数组排序后直接选取. 那么这种方法的时间复杂度是O(N log N).
C.A.R.Hoare 提出的 Quickelect 算法的平均时间复杂度达到了 O(N) . 在去递归之后, 是原地算法. 这个算法因为其简洁，高效而被广泛使用.
算法思路的C++实现如下.
int select(vector<int>& X, int k) {
int l = 0, u = X.size() - 1;
while(l < u){
swap(X[l], X[rand()%(u-l+1)+l]);
int m = l;
for(int i = l + 1; i <= u; i++) {
if(X[i] < X[l]) {
swap(X[++m], X[i]); //m在i遍历的过程中，是遍历过的元素中, 小于X[l]的元素的最大下标
}
}
swap(X[l], X[m]);
if (m == k) {
break;
} if(k < m) {
u = m - 1;
} else {
l = m + 1;
}
}
return X[k];
}
- 当 k 选定为数组的中位数时，平均所耗的时间最多.
- 当数组中有大量重复元素，或者是逆序排序的数组时，会增加运行时间. 遇到大量重复的元素时不能很快地缩小 l - u 的范围. 逆序数组会产生很多的 swap 操作.
- Worst-case peformance O(N ^ 2)
II 序列输入时使用的 Heap-Select 算法
考虑一个输入序列，要求在序列输入完毕的时候得出这个序列的第 k 大(小)的元素.
要选择第 k 小的元素时， 我们考虑用一个 k 大小的大顶堆. 对数组从头开始遍历(等价于数组线性输入)， 头 k 个元素用于建立 k 大小的大顶堆. 对于从 k + 1 到 N 的元素. 当该元素小于堆顶元素的时候，将该元素插入到堆中，将堆顶元素出堆. 遍历(输入)结束后， 堆顶元素即为我们要找的元素.
相应的选择第 k 大的元素时， 我们考虑用一个 k 大小的小顶堆.对数组从头开始遍历. 头 k 个元素用于建立 k 大小的小顶堆. 对于从 k + 1 到 N 的元素. 当该元素大于堆顶元素的时候，将该元素插入到堆中，将堆顶元素出堆. 遍历(输入)结束后， 堆顶元素即为我们要找的元素.
这样可得这个算法的时间复杂度为 O(k) + O(N * log k) ==> O(N * log k)
由于要调用空间构造堆，空间复杂度为 O(k)
关于这个算法的正确性，用归纳法， 从已经输入k的数组中挑选头k个最大(小)的元素。 然后继续下去即可。
III 三个元素的中间值
杀鸡不用牛刀，三个元素的中间值用简单的三次比较就可以搞定.
if(X[1] > X[2])
swap(X[1], X[2]);
if(X[2] > X[3])
swap(X[2], X[3]);
if(X[1] > X[2])
swap(X[1], X[2]); //自此 X[1], X[2], X[3] 从小到大有序.
IV 其他的Select算法
Median of medians 又名 BFPRT算法. 基于Blum, Floyd, Pratt, Rivest and Tarjan 1973年的论文 Time Bounds for Selection. 拥有O(N) 的 worst case performance.
Introselect 则是BFPRT算法和 Quickselect 算法的结合. 默认使用 Quickselect ，在 Quickselect 表现出比较差的运行情况时转向Median of medians. 从而也能提供O(N) 的 worst case performance.