线性时间选择
定义 在给定线性序集中n个元素和一个整数k，要求找出n个元素中第k小的数。
方法一 线性时间选择，可以使用堆排序，这样就可以在$O(n+klog_n)=O(n)_的时间内找到的k小的元素。
方法二 使用快速排序中的分块算法，对所需要选择的数组分块，分完以后再在剩余的部分中，寻找(k – 减去分块的大小)
代码如下:
但是此方法在最差的情况下需要$n^2$的时间，比如在寻找最小元素时，总是在最大的元素划分。
尽管如此，平均效率还是不错的。
方法三 我还是比较喜欢直接看代码= =……