面试题40(剑指offer)--最小的k个数

题目：

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

思路：

用快排的思想，partation函数返回值大于其左边的值，小于其右边的值。如果返回的index正好为k-1则，其前面的值就是最小的k个数，如果index小于k-1说明index后面的值也在最小的k个数里，继续在后面查找，index大于k-1时，相反。

代码：

    private static ArrayList<Integer> minNumK(int[] input, int k){
        ArrayList<Integer> resList=new ArrayList<>();
        if (input==null||input.length<=0||k<=0||input.length<k){
            return resList;
        }
        int start=0;
        int end=input.length-1;
        int index=partation(input,start,end);
        while (index!=k-1){
            if (index>k-1){
                end=index-1;
                index=partation(input,start,end);
            }else {
                start=index+1;
                index=partation(input,start,end);
            }
        }
        for (int i = 0; i < k; i++) {
            resList.add(input[i]);
        }
        return resList;
    }
    private static int partation(int[] arr, int start, int end) {
        int low=start;
        int high=end;
        int base=arr[start];
        while (low<high){
            while (arr[low]<base){
                low++;
            }
            while (arr[high]>base){
                high--;
            }
            int tmp=arr[low];
            arr[low]=arr[high];
            arr[high]=tmp;
        }
        return low;
    }