N29_输入n个整数，找出其中最小的K个数。

package new_offer;

import java.util.ArrayList;

import com.sun.net.httpserver.Authenticator.Result;

/**
 * 
输入n个整数，找出其中最小的K个数。
例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
 * @author Sonya
 * 方法一：借助排序，排完之后想要几个有几个
 * 方法二：借助O（n）当可以修改输入数组时可用
 * 方法三:O(nlogK)算法，适合处理海量数据。
 *
 */
public class N29_GetLeastNumbers_Solution {
	
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
    	ArrayList<Integer> result=new ArrayList<Integer>();
    	if(k>input.length)return result;
    	sort(input,0,input.length-1);
    	for(int i=0;i<k;i++) {
    		result.add(input[i]);
    	}
		return result;
        
    }
    //快排
    public static void sort(int[] a, int low, int high) {
        if(low>=high)
            return;
        int i = low;
        int j = high;
        int key = a[i];
        while(i<j){
        	while(i<j&&a[j]>=key){
        	j--;
        	}
        	if(i<j){
        	a[i++]=a[j];
        	}
        	while(i<j&&a[i]<=key){
        	i++;
        	}
        	if(i<j){
        	a[j--]=a[i];
        	}
        	}
        a[i] = key;
        sort(a,low,i-1);
        sort(a,i+1,high);
    }

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		N29_GetLeastNumbers_Solution n29=new N29_GetLeastNumbers_Solution();
		int []a= {4,5,1,6,2,7,3,8};
		n29.GetLeastNumbers_Solution(a, 4);
	   for(int i=0;i<a.length;i++) {
		   System.out.println(a[i]);
	   }
		System.out.println(a);
	}

}