題目描述
????輸入n個(gè)整數(shù)，找出其中最小的K個(gè)數(shù)。例如輸入4,5,1,6,2,7,3,8這8個(gè)數(shù)字，則最小的4個(gè)數(shù)字是1,2,3,4。
解題思路
????核心思想是利用快速排序，在快速排序過程中，一次排序后，基準(zhǔn)值前面的數(shù)字都小于基準(zhǔn)值，基準(zhǔn)值后面的數(shù)都大于基準(zhǔn)值。那么就可以利用這個(gè)特性，當(dāng)基準(zhǔn)值下標(biāo)對(duì)應(yīng)的位置大于k的時(shí)候，就在基準(zhǔn)值左邊利用快速排序，否則在右邊利用快速排序。

import java.util.ArrayList;
public class Solution {
    public static ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        //用來存放結(jié)構(gòu)
        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是返回的下標(biāo)值 對(duì)應(yīng)的元素個(gè)數(shù)
        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);
            }
        }
        
        //將結(jié)構(gòu)存入鏈表中
        for (int i=0;i<k;i++){
            result.add(input[i]);
            System.out.println(input[i]);
        }
        return result;
    }

    /**
     * 根據(jù)快排的改進(jìn)
     * @param array
     * @param left
     * @param right
     * @return
     */
    public static int partition(int[] array, int left, int right){
        //設(shè)置的基準(zhǔn)
        int index=array[left];
        if (left>right){
            return -1;
        }
        while (left<right){
            //后面的指針向前查找比基準(zhǔn)值小的數(shù)
            while (left<right&&array[right]>=index){
                right--;
            }
            //找到了將后面的值放到前面去
            array[left]=array[right];

            //前面的指針向后查找，找到比基準(zhǔn)值大的數(shù)
            while (left<right&&array[left]<=index){
                left++;
            }
            array[right]=array[left];
        }
        array[left]=index;  //最后將基準(zhǔn)值放到空缺的位置
        return left;
    }

}