Java代码 - 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));
- }
- }
|