简单

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个数的算法。
* 主要思想是找到集合中的中间点p，左边的数必须小于中间点位置的数，右边的必须大于它，然后判断找到的中间点是否等于K，
* 1、如果等于则找到了
* 2、如果小于(k<p),则对0-p范围的数按上面的思想继续进行查找
* 3、如果大于(k>p),则对p-len范围的数按上面的思想继续进行查找，只是不需要找k个数了，而是找p-k个数即可
*
* 找中间点是快速选择算法的核心思想，为什么要找中间点？因为我们没有必要直到这个集合的顺序是怎么样的，
* 更加没有必要去对其进行排序，我们只需要知道某个中间点的左边的数都
* 小于该中间点位置的数，反之右边的都大于，如此是递归下去，找到第K大的数只是时间问题.
*
* 其实关于查找第K个最大(小)的数是算法有好多，这只是其中比较好的一种方法，另一种较好的比如借助于大小堆也不错，充分体现了堆的强大，
* 记得有个面试题是：1亿个数据中找前100个数。就是利用大小堆完成的效率比较高.
* ------------------------------------------------
*/
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));
}
}

本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请点击举报。