题解 | #最小的K个数#

class Solution {
public:
    int partition(vector<int> & input, int left, int right)
    {
        int tmp=input[left];
        while(left<right)
        {
            while(left<right&&input[right]>=tmp)
                right--;
            if(left<right)
                input[left++]=input[right];
            while(left<right&&input[left]<=tmp)
                left++;
            if(left<right)
                input[right--]=input[left];
        }
        input[left]=tmp;
        return left;
    }
    void quicksort(vector<int> &input, int left, int right,int k)
    {
        if(left>=right)
            return ;
        int mid=partition(input,left,right);
        if(mid>k-1)
            quicksort(input,left,mid-1,k);
        if(mid<k-1)
            quicksort(input,mid+1,right,k);
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        quicksort(input,0,input.size()-1,k);
        vector<int> result(input.begin(),input.begin()+k);
        return result;
    }
};

使用快排，部分排序