问题：给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素，算法的复杂度为O(n)。
思路分析：
首先，假如我们要找最大或者最小的元素，那么只需遍历一遍序列即可，复杂度为O(n)。假如要找第k大的元素，k<=n/logn或者k>=n-nlogn时，利用堆排序，时间复杂度仍然可以达到O(n)，具体为什么还没搞懂。无论如何，如果对于任意的k，（最坏）时间复杂度要想达到O(n)，对整个序列进行排序都是不可行的（复杂度至少为nlogn）。
那么如何将复杂度降低到O(n)呢？由于我们求的仅仅是第k大的数字，那么可以不用整个对整个序列进行排序，而仅仅保证在第k大的数字前面的数字都小于这个第k大数即可。借助快排的思想，每次找一个哨兵将序列分为大于哨兵和小于哨兵的两部分，根据需要求的数是第k大选择一个子序列递归进行排序即可，而非对所有的序列都要排序。
假如能够做到在任意情况下，所选的哨兵将序列等比地分为两部分，就可以做到线性地得到结果：设子序列的长度分别为ne和n(1-e)，复杂度递推公式为T(n) = T(ne)+O(n)，时间复杂度为O(n)。
如何保证在任意情况下哨兵都会做到等比分割序列呢？传统的快速排序算法在选取哨兵时采用序列的第一个元素，这样在极端情况下会退化为等差递减的递归，也就是冒泡；随机快速排序算法对此进行了一些优化，每次随机选取哨兵，但是本质上也是一样。将序列预划分可以有效地解决这一问题：
1.将序列划分成n/5个子序列，每个子序列有5个元素，最后一个不足5个元素的子序列扔掉不要（因为目的只是为了找一个差不多的基准哨兵），任选一种排序方法对每个子序列进行排序，对每个子序列取中位数
2.取出中位数后，对n/5个中位数再取中位数，这里其实转化为中位数中求解第k大的数的子问题
3.以确定的中位数作为哨兵，进行划分序列，可以证明，当n>=75时，此时子序列近似划分为n/4和3n/4两个部分
复杂度递推公式为T(n)=T(n/5)+T(3n/4)+O(n),n>=75;T(n)=O(1),n<75
代码：
// 将序列a[]重排为mid左边的元素全部小于mid，mid右边的元素全部大于mid // 输入：序列a，序列起始下标l，终止下标r，哨兵大小mid // 输出：mid在序列a中的位置j，据此可确定划分完成的两个子序列 int part(int a[],int l,int r,int mid){ int i = l,j = r; while(i<=r && j>=l){ while(a[i]<=mid){i++;} while(a[j]>=mid){j--;} if(i>=j){ break; }else{ swap(a[i],a[j]); i++; j--; } } return j; } // 选取序列a中序号从l到r中第k小的元素 // 输入：序列a，序列起始下标l，序列终止下标r，所求的元素是第k小 // 输出：第k小的元素大小 int select(int a[],int l,int r,int k){ // 处理最小子问题：n<75 if(r-l<75){ sort(a+l, a+r+1); return a[l+k-1]; }else{ // 选出n/5个组中的中位数，每次将中位数和序列开始的位置交换， // 将中位数聚集在一起，比额外开辟内存空间然后记录下标和值要好 for(int i = 0;i <= (r-l-4)/5;i++){ sort(a+l+5*i,a+l+5*i+4); swap(a[l+i],a[l+5*i+2]); } // 获取中位数的中位数 int mid = select(a, l, l+(r-l-4)/5, ((r-l-4)/5+1)/2); // 以mid为基准进行子序列的划分 int mid_id = part(a, l, r, mid); int mid_rank = mid_id - l + 1; // 判断应该取哪个子序列进行递归 if(k == mid_rank) return a[mid_id]; else if(k > mid_rank) return select(a, mid_id+1, r, k-mid_rank); else return select(a, l, mid_id-1, k); } }