算法基础之快速选择

快速选择

找出数组排序后第k个数

• 主要思想:分治（代码跟快排很像）

•   #include<iostream>
    using namespace std;
    const int N =1e6+10;
    
    int p[N];
    int n,k;
    
    int quick_sort(int l,int r,int k){
        if(l==r) return p[l];
        //只有一个数据的数组 返回左右都可以
        int x=p[l],i=l-1,j=r+1;
        while(i<j){
            do i++; while(p[i]<x);
            //while(p[++i]<x);也可以
            do j--; while(p[j]>x);
            //while(p[--j]>x);//也可以
            if(i<j) swap(p[i],p[j]);
        }
        int sl=j-l+1;
        //求出左边<=x的元素个数 与k比较
        if(k<=sl) return quick_sort(l,j,k);
        //如果k<sl 那么p[k]一定在左边 只用递归对左边排序即可
        return quick_sort(j+1,r,k-sl);
        //如果k>sl 在右边 传入k时注意减去sl
    }
    int main(){
        cin>>n>>k;
        for(int i=0;i<n;i++){
            cin>>p[i];
        }
        cout<<quick_sort(0,n-1,k)<<endl;
    }