问题描述：从一个无序序列找一个K大的数 最直接的想法是先排序再找，但这样需要O(nlogn)的时间复杂度; 随机选择算法虽然最坏的时间复杂度为O(n^2),但对于任何输入都可以达到O(n)的时间复杂度、
思想描述：选择一个主元，经过一次快排后主元为A[p]，在A[left,right]中该主元为第p-left+1(M)大的数；若K==M ，返回主元；若K>M，则第K大的数在主元右侧，往右递归则可；若K<M，则第K大的数在主元左侧，往左递归则可；
int randomSelect(int A[],int l,int r,int k) { int temp=A[l],i=l,j=r; if(l<r) { while(i<j) { while(i<j&&A[j]>temp) j--; if(i<j) A[i++]=A[j]; while(i<j&&A[i]<temp) i++; if(i<j) A[j--]=A[i]; } A[i]=temp; } int m=i-l+1; if(k==m) return A[i]; else if(k<m) return randomSelect(A,l,i-1,k); else return randomSelect(A,i+1,r,k-m); }