求最小的K个数

题目描述
    输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
解题思路
    核心思想是利用快速排序，在快速排序过程中，一次排序后，基准值前面的数字都小于基准值，基准值后面的数都大于基准值。那么就可以利用这个特性，当基准值下标对应的位置大于k的时候，就在基准值左边利用快速排序，否则在右边利用快速排序。

import java.util.ArrayList;
public class Solution {
    public static ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        //用来存放结构
        ArrayList<Integer> result=new ArrayList<Integer>(k);
        if (input==null){
            return null;
        }
         if (k>input.length||k<=0){
            return result;
        }
        int start=0;
        int end=input.length-1;

        int index=partition(input,start,end); //一次快排之后 index是返回的下标值 对应的元素个数
        while (index!=k-1){
            //如果元素比k多，在左边利用快速排序
            if (index>k-1){
                end=index-1;
                index=partition(input,start,end);
            }else {
                //否则在右边利用快速排序
                start=index+1;
                index=partition(input,start,end);
            }
        }
        
        //将结构存入链表中
        for (int i=0;i<k;i++){
            result.add(input[i]);
            System.out.println(input[i]);
        }
        return result;
    }

    /**
     * 根据快排的改进
     * @param array
     * @param left
     * @param right
     * @return
     */
    public static int partition(int[] array, int left, int right){
        //设置的基准
        int index=array[left];
        if (left>right){
            return -1;
        }
        while (left<right){
            //后面的指针向前查找比基准值小的数
            while (left<right&&array[right]>=index){
                right--;
            }
            //找到了将后面的值放到前面去
            array[left]=array[right];

            //前面的指针向后查找，找到比基准值大的数
            while (left<right&&array[left]<=index){
                left++;
            }
            array[right]=array[left];
        }
        array[left]=index;  //最后将基准值放到空缺的位置
        return left;
    }

}