在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; }