例子：
- 按递增顺序，找出下面29个元素的第18个元素：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,23,22,46,29.
- (1) 把前面25个元素分为5(=floor(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,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(floor(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个小元素。
/* * 线性选择算法 * 给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素 * 在最坏情况下，算法randomizedSelect需要O(n2)计算时间 * 可以证明，算法randomizedSelect可以在O(n)平均时间内找出n个输入元素中的第k小元素。 */代码/**递归分治算法之线性选择 */ import java.util.Random;public class randomizedSelectTest { private static int randomizedPartition(int[] a,int p,int r){ int i=random(p,r); swap(a,i,p);//交换枢纽元素到区间左端 return partition(a,p,r); } /** * 线性选择指定数组中第k小的元素 * @param a 指定数组 * @param p 区间左端 * @param r 区间右端 * @param k 数组的大小位置 * @return 返回指定数组中第k小的元素 */ public int randomizedSelect(int[] a,int p,int r,int k){ if(p==r)return a[p]; int i=randomizedPartition(a,p,r); int j=i-p+1;//左端元素个数 //第k小的元素在左端 if(k<=j)return randomizedSelect(a,p,i,k); else//第k小的元素在右端，并且左端已经有j个比它小的元素 //所以只要找右端中的第k-j小的元素就可以 return randomizedSelect(a,i+1,r,k-j); } private static int random(int i,int j){ Random r=new Random(); return r.nextInt(j-i)+i; } private static int partition(int[] a,int p,int r){ int i,j; i=p; j=r; if((a==null)||(a.length==0)) return -1; while(i