剑指 Offer 40：最小的k个数（快速排序）

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

输入：arr = [0,1,2,1], k = 1
输出：[0]

class Solution {
private:
    void quickSort(vector<int>& arr,int l,int r){
        if(l>=r) return;
        int i=l,j=r;
        while(i<j){
            while(i<j&&arr[j]>=arr[l]) j--;
            while(i<j&&arr[i]<=arr[l]) i++;
            swap(arr[i],arr[j]);
        }
        swap(arr[l],arr[i]);
        quickSort(arr,l,i-1);
        quickSort(arr,i+1,r);
    }
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        quickSort(arr,0,arr.size()-1);
        vector<int> res;
        res.assign(arr.begin(),arr.begin()+k);
        return res;
    }
};