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

}