随机选择算法
有这样一个问题：如何从一个无序的数组里求出第\(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。）
输入 1
2第一行两个正整数n, m。
第二行为n个正整数。
输出 1
第m大的数。
样例输入 1
26 3
1 2 3 4 5 6
样例输出 1
4
代码 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
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;
}