100万個の数の中で最小の10個を探す(速排思想を利用して、速度が大きい)
主に速排の思想を利用して、解空間を区分した.
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;
}
}