1、问题的引出-求第i个顺序统计量
?
2、方法一：以期望线性时间做选择
?
3、方法二（改进）：最坏情况线性时间的选择
?
4、完整测试代码（c++）
?
5、参考资料
?
内容 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
1、问题的引出-求第i个顺序统计量 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ?什么是顺序统计量？及中位数概念
?
? ?在一个由元素组成的集合里，第i个顺序统计量（order statistic）是该集合第i小的元素。例如，最小值是第1个顺序统计量(i=1)，最大值是第n个顺序统计量(i=n)。一个中位数（median）是它所在集合的“中点元素”。当n为奇数时，中位数是唯一的；当n为偶数时，中位数有两个。问题简单的说就是：求数组中第i小的元素。
?
? ?那么问题来了：如何求一个数组里第i小的元素呢？
?
? ?常规方法：可以首先进行排序，然后取出中位数。由于排序算法（快排，堆排序，归并排序）效率能做到Θ(nlogn),所以，效率达不到线性； ?在本文中将介绍两种线性的算法，第一种期望效率是线性的，第二种效率较好，是在最坏情况下能做到线性效率。见下面两个小节；
?
2、方法一：以期望线性时间做选择 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
这是一种分治算法：以快速排序为模型：随机选取一个主元，把数组划分为两部分，A[p...q-1]的元素比A[q]小，A[q+1...r]的元素比A[q]大。与快速排序不同，如果i=q，则A[q]就是要找的第i小 的元素，返回这个值；如果i < q，则说明第i小的元素在A[p...q-1]里；如果i > q，则说明第i小的元素在A[q+1...r]里；然后在上面得到的高区间或者低区间里进行递归求取，直到找到第i小的元素。
?
下面是在A[p...q]中找到第i小元素的伪码：
?
复制代码
1 RandomSelect(A,p, q,k)//随机选择统计，以期望线性时间做选择
2 {
3 ? ? if (p==q) return A[p];
4 ? ? int pivot=Random_Partition(A,p,q);//随机选择主元，把数组进行划分为两部分
5 ? ? int i=pivot-p+1;
6 ? ? if (i==k )return A[pivot];
7 ? ? else if (i
8 ? ? else return RandomSelect(A,p,pivot-1,k);//第k小的数不在主元右边，则在左边递归选择
9 }
复制代码
?
?
在最坏情况下，数组被划分为n-1和0两部分，而第i个元素总是落在n-1的那部分里，运行时间为?(n^2);但是，除了上述很小的概率情况，其他情况都能达到线性；在平均情况下，任何顺序统计量都可以在线性时间Θ(n)内得到。
?
实现代码（c++）：
?1 //template使用模板，可处理任意类型的数据
?2 template//交换数据
?3 void Swap(T &m,T &n)
?4 {
?5 ? ? T tmp;
?6 ? ? tmp=m;
?7 ? ? m=n;
?8 ? ? n=tmp;
?9 }
10?
11 /***********随机快速排序分划程序*************/
12 template
13 int Random_Partition(vector &A,int p,int q)
14 {
15 ? ? //随机选择主元，与第一个元素交换
16 ? ? srand(time(NULL));
17 ? ? int m=rand()%(q-p+1)+p;
18 ? ? Swap(A[m],A[p]);
19 ? ? //下面与常规快排划分一样
20 ? ? T x=A[p];
21 ? ? int i=p;
22 ? ? for (int j=p+1;j<=q;j++)
23 ? ? {
24 ? ? ? ? if (A[j]
25 ? ? ? ? {
26 ? ? ? ? ? ? i=i+1;
27 ? ? ? ? ? ? Swap(A[i],A[j]);
28 ? ? ? ? }
29 ? ? }
30 ? ? Swap(A[p],A[i]);
31 ? ? return i;
32 }
33 /***********随机选择统计函数*************/
34 template
35 T RandomSelect(vector &A,int p,int q,int k)//随机选择统计，以期望线性时间做选择
36 {
37 ? ? if (p==q) return A[p];
38 ? ? int pivot=Random_Partition(A,p,q);//随机选择主元，把数组进行划分为两部分
39 ? ? int i=pivot-p+1;
40 ? ? if (i==k )return A[pivot];
41 ? ? else if (i
42 ? ? else return RandomSelect(A,p,pivot-1,k);//第k小的数不在主元右边，则在左边递归选择
43 }
复制代码
3、方法二（改进）：最坏情况线性时间的选择 ? ? ? ? ? ? ? ? ? ? ??
? ? ? 相比于上面的随机选择，我们有另一种类似的算法，它在最坏情况下也能达到O(n)。它也是基于数组的划分操作，而且利用特殊的手段保证每次划分两边的子数组都比较平衡；与上面算法不同之处是：本算法不是随机选择主元，而是采取一种特殊的方法选择“中位数”，这样能使子数组比较平衡，避免了上述的最坏情况（?(n^2)）。选出主元后，后面的处理和上述算法一致。
?
? ? ?那么问题又来了，这种特殊的手段是什么呢？
?
?
?
?
?
如上图所示：
?
1） 将输入数组的n个元素划分为n/5组，每组（上图中的每列为一组）5个元素，且至多只有一个组有剩下的n%5个元素组成
?
2） ?首先对每组中的元素（5个）进行插入排序，然后从排序后的序列中选择出中位数（图中黄色数）。
?
3） 对第2步中找出的n/5个中位数，递归调用SELECT以找出其中位数x（图中红色数）。（如果有偶数个中位数取较小的中位数）
?
这三个步骤就可以选出一个很好的主元，下面的处理和方法一一致（递归）
?
OK! 下面是完整的算法步骤：
?
1） ?将输入数组的n个元素划分为n/5组，每组（上图中的每列为一组）5个元素，且至多只有一个组有剩下的n%5个元素组成
?
2） ?首先对每组中的元素（5个）进行插入排序，然后从排序后的序列中选择出中位数（图中黄色数）。
?
3） 对第2步中找出的n/5个中位数，递归调用SELECT以找出其中位数x（图中红色数）。（如果有偶数个中位数取较小的中位数）
?
4） 调用PARTITION过程，按照中位数x对输入数组进行划分。确定中位数x的位置k。
?
5） 如果i=k，则返回x。否则，如果ik，则在高区找第(i-k)个最小元素。
?
大致伪码：
?
复制代码
?1 WorseLinearSe