在N个乱序数字中查找第k大的数字

若随机选取枢纽，线性期望时间O(N)

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int a[N];
int qs(int l,int r)
{
    int x=a[l];
    while(l<r)
    {
        while(l<r&&a[r]>=x) r--;
        a[l]=a[r];
        while(l<r&&a[l]<=x) l++;
        a[r]=a[l];
    }
    a[l]=x;
    return l;
}
int dfs(int k,int l,int r)
{
    int x=qs(l,r);
    if(x==k) cout<<a[x]<<endl;
    else if(x>k) dfs(k,l,x-1);
    else         dfs(k,x+1,r);
}
int main()
{
    int n,k;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    cin>>k;
    dfs(k-1,0,n-1);
    return 0;
}
#include<bits/stdc++.h>