简单_快速选择算法(RANDOMIZED-SELECT)_JAVA_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > JAVA > 简单_快速选择算法(RANDOMIZED-SELECT)

简单_快速选择算法(RANDOMIZED-SELECT)

 2011/10/20 8:10:45  543089122  http://jqsl2012.iteye.com  我要评论(0)
  • 摘要:packagesunfa.midNum;importjava.util.Arrays;importjava.util.Comparator;importjava.util.Random;/****参考:---------------------------------------------*http://blog.csdn.net/chen09/article/details/6531678**快速选择算法和第三名:BFPRT算法类似,都是在一个无序的数组中寻找第K小的数
  • 标签:算法
package sunfa.midNum;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;

/**
 * 
 * 参考:---------------------------------------------
 * http://blog.csdn.net/chen09/article/details/6531678
 * 
 * 快速选择算法 和 第三名:BFPRT 算法 类似,都是在一个无序的数组中寻找第K小的数,
 * 
 * 百度百科上解释了中位数的重要性及其意义,上面的2种算法都是属于中位数算法的
 * 参考:http://baike.baidu.com/view/170892.htm
 * 
 * 总结:-----------------------------------------------
 * 这个中位数之中位数算法,是用来查找未排序集合中第K个数的算法。<br>
 * 主要思想是找到集合中的中间点p,左边的数必须小于中间点位置的数,右边的必须大于它,然后判断找到的中间点是否等于K,<br>
 *  1、如果等于则找到了<br>
 *  2、如果小于(k<p),则对0-p范围的数按上面的思想继续进行查找 <br>
 *  3、如果大于(k>p),则对p-len范围的数按上面的思想继续进行查找,只是不需要找k个数了,而是找p-k个数即可<br>
 * 
 * 找中间点是快速选择算法的核心思想,为什么要找中间点?因为我们没有必要直到这个集合的顺序是怎么样的,<br>
 * 更加没有必要去对其进行排序,我们只需要知道某个中间点的左边的数都<br>
 * 小于该中间点位置的数,反之右边的都大于,如此是递归下去,找到第K大的数只是时间问题.<br>
 * 
 * 其实关于查找第K个最大(小)的数是算法有好多,这只是其中比较好的一种方法,另一种较好的比如借助于大小堆也不错,充分体现了堆的强大,<br>
 * 记得有个面试题是:1亿个数据中找前100个数。就是利用大小堆完成的效率比较高.<br>
 * ------------------------------------------------
 */
public class RandomizedSelect {
	
	private static <T> int partition(T[] a, Comparator<? super T> c, int p, int r) {
		T t = a[r - 1];
		int i = p - 1;// 中间点,小的放在i的左边,大的放右边,最后返回的i就是中间点
		for (int j = p; j < r - 1; j++) {// 从p到r-2,为什么是r-2呢?因为第r-1位置的数已被做为比较的对象了
			if (c.compare(a[j], t) <= 0) {// 从左边开始,循环的拿左边的数和最后一个数进行比较,把小的放在左边大的放右边,并且计数中位数
				i++;
				swap(a, i, j);
			}
		}
		// 在randomizedPartition方法中我们把主元放到了最后,那么中间点找到后我们得把主元放到中间点来,那么i+1便是最后得到的中间点
		swap(a, i + 1, r - 1);
		return i + 1;
	}

	private static <T> int randomizedPartition(T[] a, Comparator<? super T> c,
			int p, int r) {
		int i = new Random().nextInt(r - p) + p;// 随机选择算法
		// 随机出来的位置的数做为主元,所谓主元就是被比较的对象,我们假设有一个数的大小处于p到r的中间,这样的数被称为主元
		// 这个主元要被放到p...r的最后位置,所以这里要和最后一个元素交换
		swap(a, i, r - 1);
		return partition(a, c, p, r);
	}

	private static <T> void swap(T[] a, int i, int j) {
		T t = a[i];
		a[i] = a[j];
		a[j] = t;
	}

	private static <T> T randomizedSelect(T[] t,
			Comparator<? super T> comparator, int p, int r, int i) {
		if (p == r)// 找到第K个数
			return t[p];
		int q = randomizedPartition(t, comparator, p, r);// 找到中间点
		int k = q - p + 1;// 中间点q前面有有多少个数字
		if (i <= k)// 判断是否找到第i个数
			return randomizedSelect(t, comparator, p, q, i);// 区间查找
		else
			return randomizedSelect(t, comparator, q + 1, r, i - k);// 区间查找
	}

	private static <T> T randomizedSelect(T[] t,
			Comparator<? super T> comparator, int i) {
		return randomizedSelect(t, comparator, 0, t.length, i);
	}

	public static void main(String[] args) {
		Integer[] ints = new Integer[20];
		Random ran = new Random();
		int k = 10;
		for (int i = 0; i < ints.length; i++) {
			ints[i] = ran.nextInt(100);
		}
		Integer positiong = randomizedSelect(ints, new Comparator<Integer>() {
			public int compare(Integer o1, Integer o2) {
				return o1.intValue() - o2.intValue();
			}
		}, k);
		System.out.println("快速选择算法求出的,第"+k+"个最大数是:"+positiong);
		Arrays.sort(ints);
		System.out.println("排序后,第"+k+"个最大数是:"+ints[k-1]);
		System.out.println(Arrays.toString(ints));
	}
}

发表评论
用户名: 匿名