运用快速排序的思想，可以达到线性时间找到一串数的第K大
1 #include<cstdio> 2 #define F(i,a,b) for(int i=a;i<=b;i++) 3 4 int a[1000],n; 5 void swap(int &a,int &b){int c=a;a=b,b=c;} 6 7 int partition(int *a,int l,int r){ 8 int x=a[l],pos=l; 9 for(int i=l+1;i<=r;i++) 10 if(a[i]<x)swap(a[++pos],a[i]); 11 swap(a[l],a[pos]); 12 return pos; 13 } 14 15 int find_k(int *a,int k,int l=1,int r=n){ 16 int pos=partition(a,l,r); 17 int j=pos-l+1; 18 if(l==r)return a[l]; 19 if(k==j)return a[pos]; 20 if(k>j)return find_k(a,k-j,pos+1,r); 21 else return find_k(a,k,l,pos-1); 22 } 23 24 double findmid(){ 25 if(n&1){ 26 int k=(n>>1)+1; 27 double ans=find_k(a,k); 28 return ans; 29 }else{ 30 int k=n>>1; 31 double ans=find_k(a,k)+find_k(a,k+1); 32 return ans/2; 33 } 34 } 35 36 int main(){ 37 scanf("%d",&n); 38 F(i,1,n)scanf("%d",a+i); 39 printf("mid=%lf ",findmid()); 40 return 0; 41 }