P4690 整数排序（【入门】）

解题思路

这道题很简单：把 n 个正整数全部读进来，用 sort 从小到大排好，再按顺序输出。下面分三步实现。

**第一步，读入。**先读入 n，再用循环把 n 个数读进 numbers 数组。每个数存进结构体 Number 的 value 成员里。

**第二步，排序。**用 sort(numbers, numbers + n, cmp) 从小到大排。比较规则 cmp 返回 a.value < b.value，意思是小的在前。

**第三步，输出。**按顺序输出每个数，数字之间用一个空格隔开，最后一个数后面不能有多余的空格，最后换行。

打个比方：就像体育课给全班同学按身高从矮到高排成一列，排好之后从排头开始一个一个报数，报出来的就是升序的结果。题目里的"从小到大"就是升序，和我们排队一个道理。

可以拿小例子验证：输入 5 个数 5 3 1 4 2，排好序后输出 1 2 3 4 5，中间正好用空格隔开，末尾没有多余空格。

这道题数据量可能不小，n 最大接近五万，但排序交给 sort 处理就可以了，我们只需要把比较规则告诉它。注意输出格式要和样例一致：中间用空格隔开、末尾换行，都不能少。

参考代码

// P4690 整数排序：读入n个正整数，升序排序后输出
#include <iostream>
#include <algorithm>
using namespace std;

struct Number {
    int value;   // 数值
};

// 从小到大比较
bool cmp(const Number &a, const Number &b) {
    return a.value < b.value;
}

int main() {
    int n;
    cin >> n;
    Number numbers[100005];
    for (int i = 0; i < n; i++) cin >> numbers[i].value;
    sort(numbers, numbers + n, cmp);
    for (int i = 0; i < n; i++) {
        if (i) cout << " ";
        cout << numbers[i].value;
    }
    cout << endl;
    return 0;
}

复杂度分析

sort 的平均时间复杂度是 O(n log n)。本题 n 最大接近五万，O(n log n) 完全够快。空间上只需要一个数组存 n 个数，是 O(n)。