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));
}
}
分享到:
相关推荐
快速排序与随机快速排序,并且解决问题,计数其中重复排序次数与最大最小次数
随机算法 randomized algorithm
蓄水池算法leetcode 固定范围采样 输入大小为 n 个项目 获取 0 到 n -1 之间的随机数 根据输入返回项目[索引] 油藏取样 概括 n项的流 n不知道提前 每个项目结果的概率相等 算法 水库采样算法旨在从未知大小的总体中...
共两部分这是part1 作者: Rajeev Motwani Parbhkar Raghavan
随机霍夫变换代码、、、、、、、、、、vc6.0编程。
矩阵低秩近似,大维矩阵降复杂度矩阵计算。
University-Randomized-N-Queens:算法分析课的简短任务
中文名: 算法导论 原名: Introduction to Algorithms 作者: Thomas H. Cormen Ronald L. Rivest Charles E. Leiserson Clifford Stein 资源格式: PDF 版本: 文字版 出版社: The MIT Press书号: 978-0262033848发行...
Survey_of_Randomized_Algorithms_for_Training_Neural_Networks.pdf
matlab的素描代码随机算法课程2019年Spring CU Boulder的随机算法课程,2019年Spring, 课程信息可以在公共网站上找到 我们涵盖的实际主题以及参考链接都在此。 请参阅下面的内容,其中列出了我们所涵盖的内容。 该...
第五章 概率分析与随机化算法(Probabilistic Analysis and Randomized Algorithms) 第二部分(Part II) 排序与顺序统计(Sorting and Order Statistics) 第六章 堆排序(Heapsort) 第七章 快速排序...
algoch18并行计算机随机算法Randomized Algorithms.ppt
第五章 概率分析与随机化算法(Probabilistic Analysis and Randomized Algorithms) 第二部分(Part II) 排序与顺序统计(Sorting and Order Statistics) 第六章 堆排序(Heapsort) 第七章快速排序...
这是一组代码,这些代码通过 Python API 使用 Spark 的随机数值线性代数来实现解决大规模最小二乘问题的算法。 由杨纪言( ) 关于 给定A ( n × d ) 和b ( n × 1 ),最小二乘回归问题要解决: min_ x || Ax-b ||_...
matlab代码Randomized_Prim_Algorithm_Experiment 项目名称:实验对象提案的随机Prim算法参考论文: 源代码: 报告: 总结:这个项目是 Mitchell 教授研究项目的一部分,它是为了实证研究对象建议方法如何有效地达到...
算法导论英文版,非图片版。 I Foundations Introduction 3 1 The Role of Algorithms in Computing 5 1.1 Algorithms 5 1.2 Algorithms as a technology 11 2 Getting Started 16 2.1 Insertion sort 16 2.2 ...
LaValle 和 Kuffner - 2001 - Randomized Kinodynamic Planning1
Randomized 随机算法
普林斯顿算法编程分配2为双端队列和随机队列编写通用数据类型。 这项任务的目的是使用数组和链表实现基本数据结构,并向您介绍泛型和迭代器。 出队。 双端队列或双端队列(发音为“ deck”)是堆栈和队列的概括,...