题目的主要信息：

• 输入n个整数，输出其中最小的k个整数并按升序输出

方法一：sort排序法

具体做法：

这是最能想到，也是最简单的方法。利用sort函数对数组进行由小到大排序，然后取前k个值入vector即可。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

vector<int> GetLeastNumbers(vector<int>& input, int k) {
        vector<int> res;
        if(k == 0 || input.size() == 0) //排除特殊情况
            return res;
        sort(input.begin(), input.end()); //排序
        for(int i = 0; i < k; i++){ //因为k<=input.length,取前k小
            res.push_back(input[i]);
        }
        return res;
    }
int main(){
    int n, k;
    while(cin >> n >> k){
        vector<int> arr(n);
        for(int i = 0; i < n; i++) //输入
            cin >> arr[i];
        vector<int> output = GetLeastNumbers(arr, k); //得到最小的k个
        for(auto i: output) //输出
            cout << i << " ";
        cout << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(nlo{g}_{2}n)O(nlog\_2n)$，sort函数属于快排
• 空间复杂度：$O(1)O(1)$，无额外空间使用

方法二：堆排序

具体做法：

利用input数组中前k个元素，构建一个大小为k的大顶堆，对于后续的元素，依次比较其与堆顶的大小，若是比堆顶小，则堆顶弹出，再将新数加入堆中，直至数组结束。最后将堆顶依次弹出即是最小的k个数。

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

vector<int> GetLeastNumbers(vector<int> input, int k) {
        vector<int> res(k);
        if(k == 0 || input.size() == 0) //排除特殊情况
            return res;
        priority_queue<int> q;  
        for(int i = 0; i < k; i++)//构建一个k个大小的堆
            q.push(input[i]);
        for(int i = k; i < input.size(); i++){
            if(q.top() > input[i]){  //较小元素入堆
                q.pop();
                q.push(input[i]);
            }
        }
        for(int i = 0; i < k; i++){ //堆中元素取出入vector
            res[k - i - 1] = q.top();
            q.pop();
        }
        return res;
    }
int main(){
    int n, k;
    while(cin >> n >> k){
        vector<int> arr(n);
        for(int i = 0; i < n; i++) //输入
            cin >> arr[i];
        vector<int> output = GetLeastNumbers(arr, k); //得到最小的k个
        for(auto i: output) //输出
            cout << i << " ";
        cout << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(nlo{g}_{2}k)O(nlog\_2k)$，构建和维护大小为k的堆，需要$lo{g}_{2}klog\_2k$，加上遍历整个数组
• 空间复杂度：$O(k)O(k)$，堆空间