方法一：sort排序

1.解题思路

题意：
对于给定数组，输出其中最小的k个。
分析：
考察各类排序算法

2.解法

使用c++库函数sort()，从小到大排序后，输出前k个数。

3.具体代码

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int>ans;
        sort(input.begin(),input.end());
        for(int i=0;i<k;i++){
            ans.push_back(input[i]);
        }
        return ans;
    }
};

4.时间复杂度和空间复杂度分析

时间复杂度：，c++中的sort()是改进的快排算法。
空间复杂度：，前k个数，常数级别。

方法二：堆

1.解题思路

堆是一颗完全二叉树，可由向上调整是由空堆，逐个插入元素，来建立初始堆，
或向下调整从n/2的位置，倒着将编号n/2,n/2-1,...,1直到编号为1的结点调成堆

堆排序利用的是完全二叉树，n个结点的完全二叉树，树高log2n，叶子结点的范围是[n/2+1,n]（叶子结点中存放小顶堆的最大值或大顶堆的最小值）
在这题目，建立一个大顶堆，取堆顶元素与堆尾交换，令堆长度-1，从根结点开始向下调整即可。

2.解法

堆排序步骤：

• 初始建堆：从最后一个非叶结点开始，倒序，每次向下调整到叶子结点。
  • 向下调整：对父节点向下与其孩子结点调整（大顶堆父结点与有最大权值的孩子结点交换），从当前结点下调到叶子结点为止
• 删除根后的重建堆：堆尾覆盖堆首，堆长度-1，向下调整叶子结点。每趟将该数组元素最大值移到末尾。

3.图解

4.具体代码

class Solution {
public:
    //对父节点向下与其孩子结点调整，从当前结点下调到叶子结点为止 
    void downadjust(vector<int>&heap,int low,int high){//其中low为欲调整结点的数组下标，high一般为堆的最后一个元素的数组下标
        int i=low,j=i*2;//i为欲调整结点，j为其左孩子 
        while(j<=high){//存在孩子结点 
            if(j+1<=high&&heap[j+1]>heap[j])j=j+1;//左右孩子中最大的下标
            if(heap[j]>heap[i]){//建立大顶堆
                swap(heap[j],heap[i]);
                i=j;//保持i为欲调整结点，j为其左孩子 
                j=i*2;
            }else break;
        }
    } 
    void HeapSort(vector<int>&heap,int n){
        for(int i=n/2-1;i>=0;i--){//建堆，前n/2个是非叶子节点，其余是叶子 
            downadjust(heap,i,n-1);
        }
        for(int i=n-1;i>=0;i--){//交换堆首堆尾，然后令堆元素数量减一 
            swap(heap[0],heap[i]);
            downadjust(heap,0,i-1);
        } 
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> ans;
        HeapSort(input,input.size()); //堆排序
        for(int i=0;i<k;i++){//取前k个元素
            ans.push_back(input[i]);
        }
        return ans;
    }
};

5.时间复杂度和空间复杂度分析

时间复杂度：，建堆时间复杂度,n个元素，每次维护堆需要
空间复杂度：，仅用存储前k个元素在vector中

方法三：快速排序

1.解题思路

相关知识
快速排序，不稳定，交换类，分治思想
选择任意元素，将其放在了正确位置上（一次划分），然后递归左右。

2.解法

快速排序步骤：

• 随机选主元，对[left,right] 进行划分

  • srand((unsigned)time(NULL));//生成随机数种子
  • rand()%(b-a+1)+a;//[a,b]内的随机数 ，左右端点相差不超过RAND_MAX (32767)

• 分区的目的是传入一个数组和选定的一个元素，把所有小于那个元素的其他元素放在左边，大于的放在右边（即将选定的这个元素放在正确的位置）。

  • 具体做法是在枢轴元素右边找一个比其小的，然后移到枢轴元素左边，在枢轴元素左边找一个比其大的，然后移到枢轴元素右边

• 一次划分确定一个元素的最终位置，直到所有元素排序完成即可。

3.具体代码

class Solution {
public:
    int Partition(vector<int>&A,int left,int right){//分区的目的是传入一个数组和选定的一个元素，把所有小于那个元素的其他元素放在左边，大于的放在右边。
        int p=(int)(round(1.0*rand()/RAND_MAX*(right-left)+left));//生成[left,right]内随机数P，随机选取主元 
        swap(A[p],A[left]);
        int temp=A[left];//选取枢轴元素 
        while(left<right){
            while(A[right]>temp&&left<right)right--;//在枢轴元素右边找一个比其小的，然后移到枢轴元素左边 
            A[left]=A[right];
            while(A[left]<=temp&&left<right)left++;//在枢轴元素左边找一个比其大的，然后移到枢轴元素右边 
            A[right]=A[left];
        }
        A[left]=temp;
        return left; 
    } 
    void quicksort(vector<int>&A,int left,int right){//快速排序，调整序列中枢轴元素的位置，递归 
        if(left<right){
            int pos=Partition(A,left,right);//一次划分确定一个元素的最终位置 
            quicksort(A,left,pos-1);
            quicksort(A,pos+1,right);
        }
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> ans;
        quicksort(input,0,input.size()-1); //快速排序
        for(int i=0;i<k;i++){//取前k个元素
            ans.push_back(input[i]);
        }
        return ans;        
    }
};

4.时间复杂度和空间复杂度分析

时间复杂度：

• 最好时间复杂度：，无序时；递归树高log2n;每一层的划分总共需要遍历一遍数组(除基准外)，近似做n次比较，所以整棵树总需比较nlogn
• 最坏时间复杂度：，有序时，每次划分只得到一个比上一次划分少一个元素的子数组，递归树深度n，总需比较(n-1)+(n-2)+(n-3)+...+1=n(n-1)/2。
• 平均时间复杂度：

空间复杂度：

• 最坏空间复杂度：，划分为一个元素与其他所有元素，递归栈深度为n，所有元素全部入栈
• 平均空间复杂度：