Algorithm——一般数组元素选择问题（十一）

Algorithm——一般数组元素选择问题

《算法导论》中引出了一个一般性的数组元素选择问题：即在一个元素各异的数组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)小的了
	}
}