求第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;
}