这个算法解决问题一般是选取一个序列的第k小哥元素，那么我们很容易想到，当我们将n个数排序好以后，那么排在第k个位置的即为我们要找的元素。
通过算法学家们的研究，可以很巧妙的做到即使是最坏情况下，依然可以再线性时间内完成。
这种方法的步骤是：
1.将这n个每5个一组，不够5个的剩下的元素再组成一组。
2.取出每一组的中位数，采取任意排序方法，进行排序。
3.递归调用函数查找上一步中的所有中位数的中位数，设为x。
4.用x来分割数组，设小于x的个数为k，大于x的个数n-k。
5.若i与x相等，那么返回x；若i小于k，那么在小于x的元素中继续递归查找，否则反之。
6.当n等于1时，我们终止算法，返回元素即为所求。
依据我们的步骤，很轻易就写出代码了。
<学习笔记> 线性查找算法
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
template<class T>
void myswap(T &a, T &b) { //交换元素；
T temp;
temp = a;
a = b;
b = temp;
}
template<class T>
T partition(T list[], int a, int b, int x) { //划分方法；
int i = a;
int j = b + 1;
while (true) {
while (list[++i]<x&&i<b);
while (list[--j]>x);
if (i >= j)break;
myswap(list[i], list[j]);
}
list[a] = list[j];
list[j] = x;
return j;
}
template<class T>
void bablesort(T list[], int size) {
for (int p = 0; p<size; p++) { //冒泡排序；
for (int q = p + 1; q<size; q++) {
if (list[q]<list[p]) {
myswap(list[q], list[p]);
}
}
}
}
template<class T>
T select(T list[], int a, int b, int k) { //核心方法；
if (b ==a) { //当只有一个元素时，返回此时的值即为所寻值；
return list[a];
}
int groupnum = (b - a + 1) / 5; //每5个元素一组，分的组数；不包括不足5个的那一组；
int restnumb = (b - a + 1) % 5; //5元组划分完毕后剩下的元素；
for (int i = 0; i <groupnum; i++) {
bablesort(list+a+i*5,5); //对每个5元组进行排序；
}
if (restnumb != 0) {
bablesort(list+a+groupnum*5,restnumb); //对剩下的元素进行排序；
}
T *mids; //new一个数组来储存我们在每组中找到的中位数；
if (restnumb == 0) {
mids = new T[groupnum];
}
else {
mids = new T[groupnum+1]; //有剩余元素的情况要多一组；
}
for (int i = 0; i < groupnum; i++) {
mids[i] = list[a+i*5+2]; //将中位数放入数组中；
}
if (restnumb != 0) {
mids[groupnum] = list[a+groupnum*5+(restnumb-1)/2];
}
T x;
if(restnumb==0){ //利用递归找中位数的中位数；
x = select(mids, 0, groupnum-1, (groupnum-1)/2+1);
}
else {
x = select(mids, 0, groupnum, (groupnum) / 2 + 1);
}
delete[]mids; //释放我们的临时空间mids；
int i = partition(list, a, b,x); //以x为划分基准；
int j = i + 1 - a;
if (k <= j) {
return select(list, a, i, k); //左子串递归搜寻第k小；
}
else {
return select(list, i + 1, b, k - j);
} //右子串递归搜寻第k-j小，即为整个串的第k小；
}
