分治-快排系列一＞最小的K个数

class Solution {

    public int[] inventoryManagement(int[] stock, int cnt) {
        qsort(stock, 0, stock.length-1,cnt);
        int[] ret = new int[cnt];

        for(int i = 0; i < cnt; i++){
            ret[i] = stock[i];
        }

        return ret;
    }

    private void qsort(int[] stock, int L, int r, int cnt){
        if(L >= r) return; 

        int key = stock[new Random().nextInt(r-L+1)+L];
        int left = L-1, right = r+1, i = L;
        while(i < right){
            if(stock[i] < key) swap(stock,i++,++left);
            else if(stock[i] == key) i++;
            else swap(stock,--right,i);
        }

        //分类讨论
        //[L,left][letf+1,right-1][right,r]

        int b = right-left-1, a = left-L+1;

        if(a > cnt) qsort(stock,L,left,cnt);
        else if (a+b >= cnt) return;
        else qsort(stock,right,r,cnt-a-b);

    }

    private void swap(int[] stock, int i, int j){
        int t = stock[i];
        stock[i] = stock[j];
        stock[j] = t;
    }
}