求第k小的数 O(n)复杂度

思路：

利用快速排序的思想，把数组递归划分成两部分。设划分为x，数组左边是小于等于x，右边大于x。

关键在于寻找一个最优的划分，经过 Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan五位大牛的研究总结，提出了BFPRT 算法（也就是中位数的中位数算法）。

解决方案

利用中位数的中位数算法得到的数作为划分可以实现最优划分–在最差情况下能实现O（n）复杂度。接下来考虑可能出现许多重复的数，假设数组中所有的数全部相同，每次划分之后都是当前区间的右端点，即会退化到O（n^2）复杂度。

优化方法

代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e6+5;
int a[maxn];
int n,k;
inline int findmid(int l,int r){  //中位数的中位数 
    if(r-l<=5) return (l+r)/2;
    for(int i=0;i<(r-l)/5;++i){
        sort(a+l+i*5,a+l+i*5+5);
        swap(a[l+i],a[l+i*5+2]);
    }
    return findmid(l,l+(r-l)/5);
}
int partion(int l,int r,int &p){ //改进版partion 
    int h=findmid(l,r);
    swap(a[h],a[r-1]);
    p=0;
    int ind=l-1;
    for(int i=l;i<r-1;++i){
        if(a[i]==a[r-1]) ++p;
        if(a[i]<=a[r-1])
            swap(a[++ind],a[i]);
    }
    ++p;
    swap(a[++ind],a[r-1]);
    int i=l,j=ind-1;
    while(i<j){
        if(a[i]==a[ind]){
            while(a[j]==a[ind]) --j;
            if(i<j){
                swap(a[i],a[j]);
                --j;
            }
        }
        ++i;
    }
    return ind;
}
int solve(int l,int r){
    int p=0;
    int ind=partion(l,r,p);
    if(ind+1==k) return a[ind];
    if(ind+1>k){
        if(ind+1-p+1<=k) return a[ind];
        else return solve(l,ind-p+1);
    } 
    if(ind+1<k) return solve(ind+1,r);
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;++i) scanf("%d",&a[i]);
    printf("%d\n",solve(0,n));
    return 0;
}