最小的k个元素

题目描述：
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

关键点：1.快速排序的应用
2.也可以尝试k次冒泡

class Solution {
public:
 //快排
    int quickSort(vector<int> &arr, int begin, int end){
      int i = begin, j = end;
      int x = arr[i];
        while(i < j){
            while(i < j && arr[j] >= x) j --;
            if(i < j){
                arr[i] = arr[j];
                i ++;
            }
            while(i < j && arr[i] < x) i ++;
            if(i < j){
                arr[j] = arr[i];
                j --;
            }
        }
        arr[i] = x;
        return i;
    }
    
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k){
        vector<int> result;
        int len = input.size();
        if(len == 0 || k > len)
            return result;
        if(len == k) return input;
        
        int begin = 0;
        int end = input.size() - 1;
        int index = quickSort(input, begin, end);
        while(index != k - 1){
            if(index > k - 1){
                end = index - 1;
                index = quickSort(input, begin, end);
            }
            else{
                begin = index + 1;
                index = quickSort(input, begin, end);
            }
        }
        vector<int> res(input.begin(), input.begin() + k); 
        return res;
    }
};