算法：线性时间选择_线性时间选择算法

定义：给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素。

（1）在某些特殊情况下，很容易设计出解选择问题的线性时间算法。如：当要选择最大元素或最小元素时，显然可以在$O(n)$时间完成。（一趟比较即可）

（2）一般的选择问题，特别是中位数的选择问题似乎比最小（大）元素要难。但实际上，从渐近阶的意义上，它们是一样的。也可以在$O(n)$时间完成。

步骤：

（1）将n个输入元素划分成n/5（向上取整）个组，每组5个元素，最多只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5（向上取整）个。
（2）递归调用select来找出这n/5（向上取整）个元素的中位数。如果n/5（向上取整）是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。
划分策略示意图：

注意：

1. 设中位数的中位数是x，比x小和比x大的元素至少3*(n-5)/10个，原因：
   • 3*(n/5-1)*1/2
   • 3—中位数比x小的每一组中有3个元素比x小
   • n/5-1—有5个数的组数
   • 1/2—大概有1/2组的中位数比x小
2. 而当n≥75时，3(n-5)/10≥n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4，也就是说，长度最长为原长度的3/4。

如图，划分的部分左上是肯定比x小的（大概占1/4）右下是肯定比x大的（大概占1/4）左下和右上不确定，就算这两部分同时不比x小或比x大，划分成的子区间也能至少缩短1/4!

代码如下：

#include <bits/stdc++.h>
using namespace std;

void bubbleSort(int a[],int p,int r)
{
	for(int i=p; i<r; i++)
	{
		for(int j=i+1; j<=r; j++)
		{
			if(a[j]<a[i])swap(a[i],a[j]);
		}
	}
}

int Partition(int a[],int p,int r,int val)
{
	int pos;
	for(int q=p; q<=r; q++)
	{
		if(a[q]==val)
		{
			pos=q;
			break;
		}
	}
	swap(a[p],a[pos]);

	int i=p,j=r+1,x=a[p];
	while(1)
	{
		while(a[++i]<x&&i<r);
		while(a[--j]>x);
		if(i>=j)break;
		swap(a[i],a[j]);
	}
	a[p]=a[j];
	a[j]=x;
	return j;
}

int Select(int a[],int p,int r,int k)
{
	if(r-p<75)
	{
		bubbleSort(a,p,r);
		return a[p+k-1];
	}
	//找中位数的中位数，r-p-4即上面所说的n-5
	for(int i=0; i<=(r-p-4)/5; i++) //把每个组的中位数交换到区间[p,p+(r-p-4)/4]
	{
		int s=p+5*i,t=s+4;
		for(int j=0; j<3; j++) //冒泡排序，从后开始排，结果使得后三个数是排好顺序的（递增）
		{
			for(int n=s; n<t-j; n++)
			{
				if(a[n]>a[n+1])swap(a[n],a[n-1]);
			}
		}
		swap(a[p+i],a[s+2]);//交换每组中的中位数到前面
	}
	//(r-p-4)/5表示组数-1，则[p,p+(r-p-4)/5]的区间长度等于组数
	int x=Select(a,p,p+(r-p-4)/5,(r-p+1)/10);//求中位数的中位数
	/*
	(r-p+1)/10 = (p+(r+p-4)/5-p+1)/2
	*/
	int i=Partition(a,p,r,x),j=i-p+1;
	if(k<=j)return Select(a,p,i,k);
	else return Select(a,i+1,r,k-j);
}
int main()
{
	int x;
	//数组a存了0-79
	int a[80]= {3,1,7,6,5,9,8,2,0,4,13,11,17,16,15,19,18,12,10,14,23,21,27,26,25,29,28,22,20,24,33,31,37,36,35,39,38,32,30,34,43,41,47,46,45,49,48,42,40,44,53,51,57,56,55,59,58,52,50,54,63,61,67,66,65,69,68,62,60,64,73,71,77,76,75,79,78,72,70,74,
	           };
	cin>>x; 
	printf("第%d大的数是%d\n",x,Select(a,0,79,x));
}
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78

运行效果：