问题描述
从一个无序数组中求出第K大的数，如{5,12,7,2,9,3}，第三大的数是5，第五大的数是9.
一种思路直接先排序，取出第K个元素即可，但时间复杂度最少也是O(nlogn)，而使用快速排序的思想，时间复杂度可以降低为O(n)
思路
当对A[left,right]执行一次randPartiton之后，主元左侧的个数是确定的且都小于主元，右侧的元素均大于主元，不妨令主元是A[p]，此时A[p]是A[left,right]中第p-left+1大的数
- 若k == p - left + 1 ，那么返回该数即可
- 若k < p - left + 1，那么第k大的数在区间[left,p-1]中，即在A[left,p-1]的第K大，往左侧递归即可
- 若k > p -left + 1，那么第k大的数在区间[p+1,right]中，即在A[p+1,right]中的第K - (p-left +1)大
程序代码
int randPatition(int A[],int left,int right)
{
//生成[left,right]的随机数
int p = round((1.0*rand()/RAND_MAX)* (right - left) + left);
swap(A[left],A[p]);
int temp = A[left];
//只要left与right不相遇
while(left <right)
{
//右边
while(left < right && A[right] > temp) right --;
A[left] = A[right];
//左边
while(left < right && A[left] <= temp) left ++ ;
A[right] = A[left];
}
//left与right相遇的地方放置temp
A[left] = temp;
//返回相遇的下标
return left;
}
void randSelect(int A[],int left,int right,int k)
{ //划分序列，形成以A[p]为主元第k大的数，使其左边小于它，右边大于它
//随机选择划分，那么A[p]是该序列中第p-left+1大的
if(left == right) //边界
return ;
int p = randPatition(A,left,right);
int M = p - left + 1;
if(k == M)
return;
else if(k < M) randSelect(A,left,p-1,k);
else randSelect(A,p+1,right,k-M); //这里注意寻找第K-M大！
}
