随机选择算法

  有这样一个问题：如何从一个无序的数组里求出第$K$大的数（为了简化讨论，假设数组中的数各不相同），例如，对数组$\{ 5, 12, 7, 2, 9, 3\}$来说，第三大的数是5，第五大的数是9。

  最直接的想法就是对数组排一下序，然后直接取出第$K$大元素即可。但是这样做法需要$O(nlogn)$的时间复杂度，虽然看起来很好，但还有更优化的算法。下面介绍随机选择算法，它对任何输入都可以达到$O(n)$的期望时间复杂度。

  随机选择算法的原理类似于随机快速排序算法。可以证明虽然随机选择算法的最坏时间复杂度是$O(n^2)$，但是其对任意输入的期望时间复杂度却是$O(n)$，这意味着不存在一组特定的数据能使这个算法出现最坏情况，是个相当实用和出色的算法。

下面以一道OJ题展示一下该算法的核心代码

题目
  给定一个长度为$n(1\leq n\leq 1,000,000)$的无序正整数序列，以及另一个数$k(1\leq k\leq 1,000,000)$（关于第$k$大的数：例如序列$\{ 1, 2, 3, 4, 5, 6\}$）中第三大的数是4。）

输入

第一行两个正整数n, m。
第二行为n个正整数。

输出

第m大的数。

样例输入

6 3
1 2 3 4 5 6

样例输出

4

代码

#include "algorithm"
#include "cmath"
#include "cstdio"
#include "cstdlib"
#include "ctime"
using namespace std;
const int maxn = 1000010;
int A[maxn], n;
//随机选取主元，对区间[left, right]进行划分
int randPartition(int A[], int left, int right)
{
    //生成[left, right]内的随机数p
    int p = round(1.0 * rand() / RAND_MAX * (right - left) + left);
    //交换A[p]与A[left]
    swap(A[p], A[left]);
    //以下为不随机选择基准时的划分过程，不需要改变
    //将A[left]存放至临时变量temp
    int temp = A[left];
    //只要left与right不相遇
    while (left < right)
    {
        while (left < right && A[right] > temp)
            right--;        //反复左移right
        A[left] = A[right]; //将A[right]挪到A[left]
        while (left < right && A[left] <= temp)
            left++;         //反复右移left
        A[right] = A[left]; //将A[left]挪到A[right]
    }
    //把temp放到left和right相遇的地方
    A[left] = temp;
    //返回相遇的下标
    return left;
}
//随机选择算法，从A[left, right]中找到第K大的数，进行划分
int randSelect(int A[], int left, int right, int K)
{
    if (left == right) //边界
        return A[left];
    //划分后主元的位置为p
    int p = randPartition(A, left, right);
    //A[p]是A[left, right]中的第M大
    int M = p - left + 1;
    //找到第K大的数
    if (K == M) //找到第K大的数
        return A[p];
    if (K < M) //第K大数在主元左侧
        return randSelect(A, left, p - 1, K);
    else //第K大数在主元右侧
        return randSelect(A, p + 1, right, K - M);
}
int main()
{
    int m, n;
    while (scanf("%d%d", &n, &m) != EOF)
    {
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &A[i]);
        }
        //如果直接填m-1的话找的是第K小的数字
        printf("%d\n", randSelect(A, 0, n - 1, n - m + 1));
    }
    return 0;
}