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

最容易想到的肯定是用一个容量为4的集合记录当前的最小4个数字，并且不断的维护。这个维护过程就是一个排序过程，因此本题可以复习一些排序方式。
  这个集合可以用数组，堆以及其他数据结构。因为每次加入最小值时，都会替换出集合中的最大，所以用一个大根堆来维护，比较合适。当然也可以用一些其他的排序算法。所以第1个思路就是多种排序算法中任选一个，这里选择的堆排序。
  第2个思路就是，借鉴快排partition()方法，将整个数组分成两部分，左边是最小的4个，右边是比较大的。时间复杂度为O(n)，但这种方法修改了原数组的顺序！

写法1：这里的写法是，每次新插入数，都重写建堆。这和建立好堆后，每次调整顶点的写法不同。

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        while(input == null || k <= 0 || k > input.length)
            return list ;
        int[] arr = new int[k];  //用于放最小的k个数
        for(int i=0;i<k;i++)
            arr[i] = input[i];//先放入前k个数
        for(int i = k/2-1; i >= 0; i--){
            adjustHeap(arr,i,k-1);//将数组调整成最大堆形式
        }
        for(int i = k;i < input.length; i++){
            if(input[i]<arr[0]){ //存在更小的数字时
                arr[0]=input[i];
                adjustHeap(arr,0,k-1);//重新调整最大堆
            }
        }
        for (int i = 0; i < arr.length; i++) {
            list.add(arr[i]);
        }
        return list ;
    }
    //给一个数组，以及该数组的某个范围，将该范围构造成堆，start为最小值
     private void adjustHeap(int[] arr,int start,int end){
        int temp = arr[start];
        int child = start*2+1;
        while(child <= end){
            if(child + 1 <= end && arr[child+1] > arr[child])
                child++;
            if(arr[child] < temp)
                break;
            arr[start] = arr[child];
            start = child;
            child = child*2+1;
        }
        arr[start] = temp;
    }
}

写法2：借鉴了快排的Partition，但是并不是快速排序。有一个基准，这个基准点的左边都是较小的，右边都是较大值，只要这个基准点的索引为3，就完成了。时间复杂度为O(n)。
  具体的运行流程是，首先任取一个位置的数，以其为基准，分成两边，那么左边的数肯定小于该基准点，但是不可能取的基准点那么准，所以左边小于基准点的数的个数可能大于4，也可能小于4，因此需要近一步的划分。
  如（9,5,1,3,8,7,13,11,12）以9为基准划分后，为（5,1,3,8,7,9,13,11,12），左边小于9的有5个数（9的索引不为3），仍需划分，再对（5,1,3,8,7）进行划分此时以5为划分，则形成（1,3,5,8,7），此时左边小5的只有2个（5的索引不为3），因此对右边进行划分，右边划分（7,8）。此时拿到的值为7的索引，整体上来说，原数组变成了（1,3,5,7,8,9,13,11,12）而7这个地方的索引是3，也就是说，左边的4个较小的数已经拿到了。
  显然这个方法不太容易想到。比排序那一类方法要难想。

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        while(input == null || k<=0 || k > input.length)
            return list;
        int start = 0;//数组起始位置
        int end = input.length-1;//数组最后位置
        int index = partition(input,start,end);//任取一个数字，以其为基准，进行比较和划分
//那么index就拿到了一个基准点的位置（数组以及根据这个基准点进行了划分）
        while(index != k-1){//需要判断这个基准点的索引是否为3，为3说明左边有4个数了（完成了）
            if(index < k-1){//小于，说明左边不够4个数，因此还需要在右边部分再进行划分
                start = index+1;
                index = partition(input,start,end);
            }else{
                end = index-1;//大于，说明左边划分的数多余4个，因此对左边要进一步划分
                index = partition(input,start,end);
            }
        }
        for(int i = 0;i < k;i++){
            list.add(input[i]);
        }
        return list;
    }

     private int partition(int[] arr, int start,int end){
        int div = arr[start];//取一个基准点（这里为提升性能，应该随机取一个基准点）
        while(start < end){
            while(start < end && arr[end] >= div){
               end--;
             }       
           //交换位置，使大于div的值位于数组右边  
             int temp = arr[start];
             arr[start] = arr[end];
             arr[end] = temp;
             while(start < end && arr[start] <= div){
                start++;
             }   
           //交换位置，使小于div的值位于数组左边            
             temp = arr[start];
             arr[start] = arr[end];
             arr[end] = temp;
        }
        return start;
    }
}