P4674 对n个数降序排序（入门）

解题思路

第一步，看清题目要干什么。 输入 n 个整数，要把它们从大到小排列后输出。就像把一摞扑克牌按点数从大到小整理好，最大的一张在最上面。

第二步，认识 sort 的默认行为。 C++ 的 sort 函数默认是“从小到大”排，也就是升序。比如数组里是 3、1、2，sort 之后会变成 1、2、3。可是这题要的是从大到小（降序），直接用它排就不行，怎么办？

第三步，写一个比较函数告诉 sort 规则。 我们给 sort 传一个比较函数 cmp，规定：“当 num1 大于 num2 时，就认为 num1 应该排在 num2 的前面。” sort 就会照着这个规则把大的数一个个放到前面，最后得到从大到小的顺序。比如 5、2、8 这三个数：先比较发现 5 比 2 大，5 在前；再比较 8 比 5 大，8 又排到 5 前面，最终排成 8、5、2。

第四步，按要求输出。 排完序后，把 n 个数依次输出，数字之间用空格隔开。注意第一个数前面不能输出空格，最后一个数后面要换行。代码里用 if(i) 来判断：只有不是第一个数时，才在它前面输出一个空格。

第五步，想想边界情况。

• 如果 n=1，只有一个数，不需要排序，直接把它输出就行。
• 如果所有数都一样，比如全是 7，无论怎么排都是 7、7、7，比较函数“分不出胜负”也不影响结果。
• n 最多 100，数字范围 1~1000，数组开 105 就足够，不用担心越界。

参考代码

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

int values[105]; // 存放要排序的 n 个整数

// 比较函数：num1 大于 num2 时，num1 排在 num2 前面，实现从大到小
bool cmp(int num1, int num2) {
    return num1 > num2;
}

int main() {
    int n; // 数字的个数
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> values[i]; // 读入第 i 个数字
    }
    sort(values, values + n, cmp); // 从大到小排序
    for (int i = 0; i < n; i++) {
        if (i) cout << ' '; // 第一个数前面不输出空格，后面的数前输出空格
        cout << values[i];
    }
    cout << endl; // 末尾换行
    return 0;
}

复杂度分析

sort 排序 n 个数，时间复杂度 O(n log n)，n ≤ 100，几百次操作，秒完成。空间复杂度 O(n)，用来存 n 个整数。