《算法导论》中引出了一个一般性的数组元素选择问题：即在一个元素各异的数组A中，选择其中第i小的元素（即如果i=1,则表明选择最小的那个元素）。
该算法的伪代码如下，它使用了之前介绍快速排序中的随机子数组划分方法：
RANDOMIZED-SELECT(A, p, r, i) if p == r return A [p] q = RANDOMIZED-PARTITION(A, p, r) k = q - p + 1 if i == k return A[q] else if i < k return RANDOMIZED-SELECT(A, p, q - 1, i) else return RANDOMIZED-SELECT(A, q + 1, r, i - k)此算法的Java实现如下： /** * * 在给定的数组下标区间范围内,根据选定的主元划分子数组 * * @param A * 待排序的主数组 * @param p * 子数组下标的左边界 * @param r * 子数组下标的右边界 * @return 得到的子数组划分分界下标值 */ private int partition(int[] A, int p, int r) { int pivot = A[r];// pivot element int i = p - 1; for (int j = p; j < r; j++) { // 当pivot >= // A[j]时,下标为j的元素就是需要与下标为i的元素进行交换的元素;下表为i的元素是前面那些比pivot大的元素的下标;即,在发现一个元素比pivot小时,就将此元素与之前的比pivot元素大的元素进行交换;这样比pivot小的元素总会出现在数组左边,并连续出现. if (A[j] <= pivot) { i++;// 下标自加1;每次自加1后,当前下标i指向的元素都比pivot大 exchange(A, i, j); } } // for循环结束后此时数组A[p...r]的状态是: // 对于任意下标k,如果k在[p,i]区间内,总有A[k] <= pivot; // 对于任意下标k,如果k在[i+1,j]区间内,总有A[k] > pivot; // 若下标k = r,则A[r] = pivot; exchange(A, i + 1, r);// 将A[i+1]与A[r]交换,此时会有小远(i+1)下标的元素的值都小于等于pivot;大于(i+1)下标的元素值都大于pivot return i + 1; } // 用于随机抽样 private Random util = new Random(); /** * * 加入随机抽样的数组划分算法 * * @param A * 待排序的数组A * @param p * 待排序的子数组下标左边界 * @param r * 带排序的子数组下标右边界 * @return 得到的子数组划分分界下标值 */ public int randomizedPartition(int[] A, int p, int r) { int i = util.nextInt(r - p + 1)/* 区间[0,r-p+1) */ + p;// 随机生成一个在区间[p,r]之间的下标值 exchange(A, i, r);// 保证子数组划分所需要的pivot element是随机从A[p...r]中选取的 return partition(A, p, r);// 调用常规子数组划分函数,进行子数组划分 } /** * 一种解决选择问题的分治算法：返回数组A(不包含相同元素)中下标范围[p...r]内的第i小的元素;i从1开始算,i=1则说明选择A[p...r]中最小的那个元素 * */ public int randomizedSelect(int[] A, int p, int r, int i) { if (p == r) return A[p];//如果指定的下标范围内只有一个元素,那当前元素就是所需要的第i小的元素 int q = randomizedPartition(A, p, r);//使用随机子数组划分方法,借助一个随机主元去划分子数组(可能为空);返回的q的下标是当前主元的下标 //在上一步划分完子数组后,A[p...r]实际上可以看做被划分成了三个子数组区间:A[p...q-1] =< A[q] < A[q+1...r];此时主元A[q]在整个子数组A[p...r]中已经是排好序的了 int k = q - p + 1;//计算子数组A[p...q]内的元素个数 if (i == k)//如果i==k,则说明此次的主元A[q]就是要选择的第i小的元素,此时就直接返回;否则下面两步就要确定要选的元素是在子数组A[p...q-1]还是在A[q+1...r]中了 return A[q]; else if (i < k)//i < k,说明待选择的元素在子数组中A[p...q-1]中,随后继续递归查找 return randomizedSelect(A, p, q - 1, i); else //i > k,说明待选择的元素在子数组A[q+1...r]中,随后继续递归查找; return randomizedSelect(A, q + 1, r, i - k);//同时要注意,此时我们已知了A[p...q]中的元素(总共有k个)都是比待选择的元素小的,那么在子数组A[q+1...r]中,待选择的元素应该是第(i-k)小的了 }完整的测试代码是： public class SortAlgor { public static void main(String[] args) { int[] A = { 2, 5, 10, 8, 9, 12, 15, 4 }; SortAlgor algorithm = new SortAlgor(); System.out.println(algorithm.randomizedSelect(A, 0, A.length-1, 3));//返回5 } /** * * 在给定的数组下标区间范围内,根据选定的主元划分子数组 * * @param A * 待排序的主数组 * @param p * 子数组下标的左边界 * @param r * 子数组下标的右边界 * @return 得到的子数组划分分界下标值 */ private int partition(int[] A, int p, int r) { int pivot = A[r];// pivot element int i = p - 1; for (int j = p; j < r; j++) { // 当pivot >= // A[j]时,下标为j的元素就是需要与下标为i的元素进行交换的元素;下表为i的元素是前面那些比pivot大的元素的下标;即,在发现一个元素比pivot小时,就将此元素与之前的比pivot元素大的元素进行交换;这样比pivot小的元素总会出现在数组左边,并连续出现. if (A[j] <= pivot) { i++;// 下标自加1;每次自加1后,当前下标i指向的元素都比pivot大 exchange(A, i, j); } } // for循环结束后此时数组A[p...r]的状态是: // 对于任意下标k,如果k在[p,i]区间内,总有A[k] <= pivot; // 对于任意下标k,如果k在[i+1,j]区间内,总有A[k] > pivot; // 若下标k = r,则A[r] = pivot; exchange(A, i + 1, r);// 将A[i+1]与A[r]交换,此时会有小远(i+1)下标的元素的值都小于等于pivot;大于(i+1)下标的元素值都大于pivot return i + 1; } // 用于随机抽样 private Random util = new Random(); /** * * 加入随机抽样的数组划分算法 * * @param A * 待排序的数组A * @param p * 待排序的子数组下标左边界 * @param r * 带排序的子数组下标右边界 * @return 得到的子数组划分分界下标值 */ public int randomizedPartition(int[] A, int p, int r) { int i = util.nextInt(r - p + 1)/* 区间[0,r-p+1) */ + p;// 随机生成一个在区间[p,r]之间的下标值 exchange(A, i, r);// 保证子数组划分所需要的pivot element是随机从A[p...r]中选取的 return partition(A, p, r);// 调用常规子数组划分函数,进行子数组划分 } /** * 一种解决选择问题的分治算法：返回数组A(不包含相同元素)中下标范围[p...r]内的第i小的元素;i从1开始算,i=1则说明选择A[p...r]中最小的那个元素 * */ public int randomizedSelect(int[] A, int p, int r, int i) { if (p == r) return A[p];//如果指定的下标范围内只有一个元素,那当前元素就是所需要的第i小的元素 int q = randomizedPartition(A, p, r);//使用随机子数组划分方法,借助一个随机主元去划分子数组(可能为空);返回的q的下标是当前主元的下标 //在上一步划分完子数组后,A[p...r]实际上可以看做被划分成了三个子数组区间:A[p...q-1] =< A[q] < A[q+1...r];此时主元A[q]在整个子数组A[p...r]中已经是排好序的了 int k = q - p + 1;//计算子数组A[p...q]内的元素个数 if (i == k)//如果i==k,则说明此次的主元A[q]就是要选择的第i小的元素,此时就直接返回;否则下面两步就要确定要选的元素是在子数组A[p...q-1]还是在A[q+1...r]中了 return A[q]; else if (i < k)//i < k,说明待选择的元素在子数组中A[p...q-1]中,随后继续递归查找 return randomizedSelect(A, p, q - 1, i); else //i > k,说明待选择的元素在子数组A[q+1...r]中,随后继续递归查找; return randomizedSelect(A, q + 1, r, i - k);//同时要注意,此时我们已知了A[p...q]中的元素(总共有k个)都是比待选择的元素小的,那么在子数组A[q+1...r]中,待选择的元素应该是第(i-k)小的了 } }
