剑指 Offer 40. 最小的k个数 (opens new window)

解题思路：快排。利用快排的性质，假设数组base左侧的个数为leftnum，那么它们一定是整个局部数组中最小的leftnum个数。

每轮确定好当前base的位置后，判断数组base左侧的个数是否比k小，如果小则剩下的k-leftnum个最小值就在base右侧找出；如果大则k个最小数都在base左侧找出。

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] res=new int[k];
        quicksort(arr,0,arr.length-1,k);
        for(int i=0;i<k;i++)
        res[i]=arr[i];
        return res;
    }
    public void quicksort(int[] arr,int low,int high,int k){
        if(low>high||k==0) return;
        int left=low;
        int right=high;
        int base=arr[left];
        while(low<high){
            while(low<high&&arr[high]>=base) high--;
            while(low<high&&arr[low]<=base) low++;
            if(low<high){
                int temp=arr[high];
                arr[high]=arr[low];
                arr[low]=temp;
            }
        }
        arr[left]=arr[low];
        arr[low]=base;

        if(low-left+1<=k){
            quicksort(arr,low+1,right,k-(low-left+1));
            return;
        }
        else{
           quicksort(arr,left,low,k);
           return;
        }
    }
}