public class QuickSelect {
private static Comparable median3(Comparable[] data , int left, int right){
int center = (left + right) /2 ;
if(data[center].compareTo(data[left]) < 0)
swapReferences(data, left, center);
if(data[right].compareTo(data[left]) < 0)
swapReferences(data, left, right);
if(data[right].compareTo(data[center]) < 0)
swapReferences(data, center, right);
swapReferences(data, center, right -1);
return data[right - 1];
}
private static void swapReferences(Comparable[] data, int src, int des){
Comparable tmp;
tmp = data[des];
data[des] = data[src];
data[src] = tmp;
}
private static void quickSelect(Comparable[] data, int left, int right, int k){
if(left + CUTOFF <= right){
Comparable pivot = median3(data, left, right);
int i = left;
int j= right -1;
for(; ;){
while(data[++i].compareTo(pivot) < 0){}
while(data[--j].compareTo(pivot) > 0) {}
if(i < j)
swapReferences(data, i, j);
else
break;
}
swapReferences(data, i, right - 1);
if(k <= i){
quickSelect(data,left, i - 1, k);
//return data[left+k-1];
}
else{
quickSelect(data, i + 1, right, k);
//return data[left + k -1];
}
}
else{
insertionSort(data, left, right);
//return data[left + k -1];
}
}
private static void insertionSort(Comparable[] data, int left, int right){
int j;
for(int p = left + 1; p <= right; p++){
Comparable tmp = data[p];
for(j = p; j > left && tmp.compareTo(data[j-1]) < 0; j--)
data[j] = data[j-1];
data[j] = tmp;
}
}
public static Comparable quickSelect(Comparable[] data, int k){
quickSelect(data, 0, data.length - 1, k);
return data[k -1];
}
public static void main(String[] args){
Comparable[] a = new Comparable[20];
for(int i = 0; i < a.length; i ++)
a[i] = (int) (Math.random() * 100);
for(int i = 0; i < a.length; i ++)
System.out.print(a[i] + ", ");
System.out.println("//");
Comparable b = quickSelect(a, 8);
for(int i = 0; i< a.length; i++)
System.out.print(a[i] +", ");
System.out.println("//");
System.out.println(b);
}
private final static int CUTOFF = 10;
}
5, 8, 37, 72, 67, 64, 60, 32, 0, 95, 43, 3, 7, 16, 11, 75, 29, 54, 41, 13, //
5, 8, 11, 7, 3, 0, 13, 16, 29, 32, 43, 67, 72, 60, 37, 75, 64, 54, 41, 95, //
16
分享到:
相关推荐
用java实现银行家调度算法,避免进程死锁!
java实现FCM聚类算法java实现FCM聚类算法java实现FCM聚类算法java实现FCM聚类算法
java实现网页排名算法java实现网页排名算法java实现网页排名算法java实现网页排名算法java实现网页排名算法
java实现银行家算法 java实现银行家算法
快速幂 Java实现快速幂算法
所谓的二分查找,指的是将待查的数据序列而分化,然后对比中间中间值和要查找值,判断结果,相等则找到,小于则在左边的子序列找,大于则在右边的子序列找
java实现弗洛伊德算法 经典java实现弗洛伊德算法 经典java实现弗洛伊德算法 经典java实现弗洛伊德算法 经典java实现弗洛伊德算法 经典
java实现蚁群算法解决旅行商问题TSP问题.zipjava实现蚁群算法解决旅行商问题TSP问题.zipjava实现蚁群算法解决旅行商问题TSP问题.zipjava实现蚁群算法解决旅行商问题TSP问题.zipjava实现蚁群算法解决旅行商问题TSP...
java 几种查找算法
普通克里金算法实现,使用java进行的一个普通克里金算法实现,本代码开源
java实现银行家算法(GUI界面)A+报告
利用JAVA语言编程实现的经典A*算法,复制到eclipse即可运行
Java 二分查找算法的示例代码。 欢迎访问个人博客。 http://blog.csdn.net/evanwang1987
Java实现对Weka算法的应用案例。Java实现对Weka算法的应用案例。Java实现对Weka算法的应用案例。
主要介绍了Java实现的快速查找算法,结合具体实例形式分析了快速查找算法的原理与相关实现技巧,需要的朋友可以参考下
对存放在数组中的数据 实现了快速查找算法 利用随机函数产生10000个随机数
基于java实现协同过滤算法,并附带测试集,假设用户喜欢跟他过去喜欢的物品相似的物品 ,历史上相似的物品在未来也相似 ,给定用户u,找到他过去喜欢的物品的集合R(u). , 把和R(u)相似的物品推荐给u.
java 快速排序 折半查找的界面实现 (递归与分治法)
java实现logistic回归算法 java实现logistic回归算法 java实现logistic回归算法
java版的DBSCAN聚类算法实现,是典型的算法思路实现,遍历未访问的所有点,如果是核心点,就新建一个簇,然后遍历其邻域内的所有点集A,不断扩展,如果簇内的点时核心点,就将其邻域所有点纳入点集A,并从点集移除已...