最小的K个数

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

 方法一：快排

class Solution {
public:
    int par(vector<int>&a,int begin,int end)
    {
        int low=begin;
        int high=end;
        int pivot=a[low];
        while(low<high)
        {
            while(low<high&&a[high]>=pivot) high--;
            a[low]=a[high];
            while(low<high&&a[low]<=pivot) low++;
            a[high]=a[low];
        }
        a[low]=pivot;
        return low;
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {     
        if(input.size()==0||input.size()<k||k<=0) return vector<int>();//这里一定的添加K<=0 不然会超时
        
        int len=input.size();
        if(len==k) return input;
        int l=0;
        int r=len-1;
        int index=par(input,l,r);
        while(index!=(k-1))
        {
            if(index>(k-1))
            {
                r=index-1;
                index=par(input,l,r);
            }
            else
            {
                l=index+1;
                index=par(input,l,r);
            }
        }
        vector<int>res(input.begin(),input.begin()+k);
        return res;   
        
        
    }
};

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        //选择排序算法
        vector<int>res;
        if(input.size()==0||input.size()<k) return res;
        for(int i=0;i<k;i++)//进行k次选择，每次选择都是从剩下的整数中选择最小的元素，j用来从无序区中遍历元素，index标记最小元素的下标
        {
            int index=i;
            for(int j=i+1;j<input.size();j++)
            {
                if(input[index]>input[j])
                {
                    index=j;
                }
            }
            res.push_back(input[index]);//把最小的元素放入
            if(index!=i)//最小的元素不是i本身，则交换
                swap(input[i],input[index]);
        }
        return res;
};

方法二：选择排序；（部分排序） 

方法三：全排序

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {

        vector<int>res;     
        if(input.size()==0||input.size()<k) return res;
        
        sort(input.begin(),input.end());
        for(int i=0;i<k;i++)
            res.push_back(input[i]);
       return res;
};