P4682 对n个数字排序（入门）

解题思路

第一步，读入数据。 第一行是数字个数 n，第二行是 n 个数字。用 cin 依次读进数组 nums。cin 读数字时会自动跳过空格和换行，所以即使第二行的数字分成了好几行，程序也能正确读进来，不用我们操心。

第二步，从小到大排序。 sort(nums, nums + n) 表示把数组从下标 0 到 n-1 这 n 个元素从小到大排序。理解这个写法：nums 是起点，nums + n 指向数组最后一个元素后面的那个位置，这是一个"左闭右开"的区间，sort 会把 [nums, nums+n) 里的元素统统排好。

第三步，输出。 用循环从下标 0 走到 n-1，除了最后一个数字（下标 n-1）后面不跟空格，其余每个数字后面跟一个空格，最后换行。

用样例验证。 输入 10 个数 5 3 2 2 1 1 4 5 9 4，排序后得到 1 1 2 2 3 4 4 5 5 9，和样例输出完全一致。注意这里有重复数字（两个 1、两个 2、两个 4、两个 5），排序后重复的数字挨在一起，直接输出即可，这道题不需要去重。

边界情况： n 最大 100，数组开 nums[105] 足够；每个数字范围是 1~1000，用 int 类型完全装得下。这道题只要会调用 sort() 就能做对，是练习排序基础的好题目。

参考代码

// P4682 对n个数字排序：把n个整数从小到大排序后输出
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    int nums[105];
    for (int i = 0; i < n; i++) cin >> nums[i];
    sort(nums, nums + n); // 从小到大排序
    for (int i = 0; i < n; i++) {
        cout << nums[i];
        if (i < n - 1) cout << " ";
    }
    cout << endl;
    return 0;
}

复杂度分析

sort() 底层是快速排序，平均时间复杂度 O(n log n)。n 最大只有 100，即使最坏情况也很快。除了排序用的数组，没有使用其他额外的大内存，空间复杂度 O(n)。