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;}}