线性时间选择（Top K）问题（Java）
1、前置介绍
定义
选择问题（select problem）是指在n个元素的集合中，选出某个元素值大小在集合中处于第k位的元素，即所谓的求第k小元素问题(kth-smallest)。
元素选择问题的一般提法
给定具有n个元素的一个线性序集和一个整数k，其中， l<=k<=n ，题目要求找出这n个元素中 第k小 的元素， 即如果将这n 个元素依其线性序排列时，排在第k个的元素即为要找的元素。
易知，
- 当
k=l时，就是要找最小元素； - 当
k=n时，就是要找最大元素； - 当
k= (n+l)/2时，称为找中位数。
在某些特殊情况下，很容易设计出解选择问题的线性时间算法。
例如，找n个元素的最小元素和最大元素显然可以在O(n)时间完成。如果 k<=n/logn , 通过堆排序算法可以在O(n+klogn) = O(n)时间内找出第k小元素。 当 k>=n-n/logn 时也一样。
2、分治法求解
一般的选择问题， 特别是中位数的选择问题似乎比找最小元素要难。但事实上， 从渐近阶的意义上看，它们是一样的。
一般的选择问题也可以在OCn) 时间内得到解决。
设原表长度为n，假定经过一趟划分，分成左右两个子表，其中左子表是主元及其左边元素的子表，设其长度为j，右子表是主元右边元素的子表。那么，若
k=j，则主元就是第k小元素；否则若k<j，第k小元素必定在左子表中，需求解的子问题成为在左子表中求第k小元素；若k>j，则第k小元素必定在右子表中，需求解的子问题成为在右子表中求第k-j小元素。
下面要讨论解一般的选择问题的分治算法 randomizedSelect 。该算法实际上是 模仿快速排序算法 设计出来的。
其基本思想也是对输入数组进行 递归划分 。与快速排序算法不同的是，它 只对划分出的子数组之一 进行递归处理。
随机选主元算法
假定表中元素各不相同，并且随机选择主元，即在下标区间[left,right]中随机选择一个下标r，以该下标处的元素为主元。
要找数组arr[0:n-1]中第K小元素只要调用randomizedSelect(arr, 0, n -1, k)即可。
具体算法可描述如下：
privatestaticComparablerandomizedSelect(intp,intr,intk) { if (p==r) returna[p]; inti=randomizedpartition(p,r), j=i-p+1; if (k<=j) { returnrandomizedSelect(p,i,k); } else { returnrandomizedSelect(i+1,r,k-j); } }
3、代码实现
- 将n个输入元素划分成⌈n/5⌉个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共⌈n/5⌉个。
- 递归调用select来找出这⌈n/5⌉个元素的中位数。如果⌈n/5⌉是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。
例子
解题步骤
(1)把前面25个元素分为5(=⌊29/5⌋)组:
(8,31,60,33,17)，(4,51,57,49,35)，(11,43,37,3,13)，(52,6,19,25,32)，(54,16,5,41,7)
(2)提取每一组的中值元素，构成集合{31,49,13,25,16}；
(3)递归地使用算法求取该集合的中值，得到m=25:
(4)根据m=25,把29个元素划分为3个子数组：
- P = {8,17,4,11,3,13,6,19,16,5,7,23,22}
- Q = {25}
- R = {31,60,33,51,57,49,35,43,37,52,32,54,41,46,29}
(5)由于P=13、Q=1、k=18，所以放弃P、Q，使k=18-13-1=4,对R递归地执行本算法：
(6)将R划分成3(⌊18/5⌋)组：{31,60,33，51,57}，{49,35，43,37,52}，{32,54,41,46,29}
(7)求取这3组元素的中值元素分别为：{51,43,41}，这个集合的中值元素是43；
(8)根据43将R划分成3组：
{31,33,35,37,32,41,29},{43},{60,51,57,49,52,54,46}
(9)因为k=4,第一个子数组的元素个数大于k,所以放弃后面两个子数组，以k=4对第一个子
数组递归调用本算法；
(10)将这个子数组分成5个元素的一组：{31,33,35,37,32},取其中值元素为33：
(11)根据33，把第一个子数组划分成{31,32,29},{33},{35,37,41}
(12)因为k=4,而第一、第二个子数组的元素个数为4，所以33即为所求取的第18个小元素。
privatestaticComparableselect (intp, intr, intk) { if (r-p<5) { // 如果元素个数小于5，可以直接返回结果// 用某个简单排序算法对数组a[p:r]排序;bubbleSort(p, r); returna[p+k-1]; } // 将a[p + 5 * i]至a[p + 5 * i + 4]的第3小元素// 与a[p+i]交换位置;// 找中位数的中位数，r-p-4即上面所说的n-5for (inti=0; i<= (r-p-4) /5; i++) { ints=p+5*i, t=s+4; for (intj=0; j<3; j++) { bubble(s, t-j); } MyMath.swap(a, p+i, s+2); } Comparablex=select(p, p+ (r-p-4) /5, (r-p+6)/10); inti=partition(p,r,x), j=i-p+1; if (k<=j) { returnselect(p,i,k); } else { returnselect(i+1,r,k-j); } }
4、复杂度分析
在最坏情况下，算法randomizedSelect需要O(n2)计算时间（在找最小元素时，总是在最大元素处划分）
但可以证明，算法randomizedSelect可以在O(n)平均时间内找出n个输入元素中的第k小元素。
如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的ε倍(0<ε<1是某个正常数)，那么就可以在最坏情况下用O(n)时间完成选择任务。
例如，若ε=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间T(n)满足递归式T(n)≤T(9n/10)+O(n) 。
由此可得T(n)=O(n)。
设所有元素互不相同。在这种情况下，找出的基准x至少比3(n-5)/10个元素大，因为在每一组中有2个元素小于本组的中位数，而n/5个中位数中又有(n-5)/10个小于基准x。同理，基准x也至少比3(n-5)/10个元素小。而当n≥75时，3(n-5)/10≥n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4。(备注：就是说明递归子问题规模是下降的，划分后的两个子数组分别至多有3n/4个元素)
上述算法将每一组的大小定为5，并选取75作为是否作递归调用的分界点。这2点保证了T(n)的递归式中2个自变量之和n/5+3n/4=19n/20=εn，0<ε<1。这是使T(n)=O(n)的关键之处。当然，除了5和75之外，还有其他选择。
递归树
5、扩展
分组为什么5个元素一组？3个一组或7个一组行不行？
分析：递归调用
1、求x的工作量与中位数集合的规模有关,其值=n/t有关，t为每组元素数，t越大，其规模越小
2、规约后子问题大小与分组元素数t有关，t越大，子问题规模大。
6、参考资料
- 算法分析与设计（第四版）
