题目描述：
输入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;
}
};
