随机选择算法-选择第K大

问题描述

从一个无序数组中求出第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大！
}