主要利用了快排的思想,划分解空间。
package net.bobo;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class MinTenNumbers {
//100万的数据量
private static final int TOTAL = 1000000;
//驱动方法
public static int[] minTenNumbers(int[] data){
return minTenNumbers(data,data.length - 1);
}
//交换数组两个数
private static void swap(int[] data,int i,int j){
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
//实际的工作方法,利用到了快速排序的思想
private static int[] minTenNumbers(int[] data,int end){
if(end < 20){
Arrays.sort(data,0,end+1);
return Arrays.copyOf(data, 10);
}
//下面的工作是确保要比较的pivot必然大于9个数
int step = end/10;
int[] temps = new int[10];
for(int i = 0;i<10;i++){
temps[i] = data[i*step];
}
Arrays.sort(temps);
int max = temps[9];
int maxIndex = 0;
for(int i =0;i<10;i++){
if(data[i*step] == max){
maxIndex = i*step;
}
}
swap(data,0,maxIndex);
int pivot = data[0];
int i = 1;
int j = end;
for(;;){
if(i >= j) break;
if(data[i] > pivot){
if(data[j] <= pivot){
swap(data,i,j);
i++;
j--;
}else if(data[j] > pivot){
j--;
}
}else{
i++;
}
}
swap(data,0,i-1);
//递归计算前半部分,因为后半部分肯定没有最小的10个数,这是将解空间减少的关键
return minTenNumbers(data, i);
}
/**
* @param args
*/
public static void main(String[] args) {
for(;;){
int[] data = generateNumbers();
long start = System.currentTimeMillis();
int[] results = minTenNumbers(data);
for(int i = 0;i < 10;++i){
if(i != results[i]){
System.err.println("出错了!!!!!!!!");
}
}
System.out.println("用时:"+(System.currentTimeMillis()-start));
data = generateNumbers();
start = System.currentTimeMillis();
Arrays.sort(data);
System.out.println("排序用时:"+(System.currentTimeMillis()-start));
}
}
private static int[] generateNumbers(){
List<Integer> numbers = new ArrayList<Integer>();
for(int i = 0;i < TOTAL;i++){
numbers.add(i);
}
Collections.shuffle(numbers);
int[] results = new int[numbers.size()];
for(int i = 0; i < TOTAL; i++){
results[i] = numbers.get(i).intValue();
}
return results;
}
}
分享到:
相关推荐
从一亿个数中找出最大的100个 或者n个 用了个堆
从一亿个数中找出最大的100个 或者n个 用了个堆从一亿个数中找出最大的100个 或者n个 用了个堆
连续输入5个100以内的数字,统计和、最小和最大
指针 ~~编写一个函数,将数组中n个数按反序存放。 实验步骤与要求: 在主函数中输入10个数,并输出排好序的数。 编写函数invert()将10个数按反序存放。
如何从1000000个数中找出出现次数最多的50个数
编写程序:从10个数中求出最大值,最小值 和平均值?
利用栈把10进制数转化为2进制数,利用栈的先进后出的原理。
用VC++链表做的奇偶分离,按大小排列,总共随即产生100万数
打印出所有的"水仙花数(narcissus number)",所谓"水仙花数"是指一个三位数, 其各位数字立方和等于该数本身。例如:153是一个"水仙花数",因为153=1...利用for循环控制100-999个数,每个数分解出个位,十位,百位。 */
ListView快速显示100万条数据用时1秒 最精简单代码演示快速显示
描述: 有一张城市地图,图中的顶点为城市,无向边代表两个城市间的连通关系,边上的权为在这两个城市之间修建高速公路的造价,研究后发现,这个地图有一个特点,即任一对城市都是连通的。现在的问题是,要修建若干...
100万吨年建筑垃圾资源化利用处置项目环境影响报告表【模板】.pdf
C语言实现随机产生10个50~100的数的程序实现
100万以内的素数表
100万条大数据,课直接使用,已经排好序了。全是流数据
微机原理与接口技术实验 以buff开始的内存单元中有10个有符号数(字节型): -37、28、-115、-2、98、-100、93、120、56、-99 请编写程序找出最大的数存入MAX单元中,同时也找出最小的数存入MIN单元中。
找出一个二维数组的鞍点,即该位置上的元素在该行上最大、在列上最小(也可能没有鞍点)。
11-王小华-2009-青海100万吨钾肥综合利用工程_工艺技术与安全生产分析.pdf
多久才能拥有100万(二)_Excel期数函数NPER的应用.rar,假设基金的年收益率是15%,目前账户余额为10万元,今后每年末追加1万元,那么要经过多久才能变成100万元?
编写一个在具有m行n列的二维数组各元素中找出最大元和最小元并显示在屏幕上的函数模板,并通过主函数对它进行调用以验证其正确性。例如,可设计该函数模板的原型为: template <class Type> void maxMin (Type *A,...