P4681 身高排序（入门）

解题思路

第一步，读入身高。 把 n 个身高依次存进数组 heights，比如输入 126、137、168、126、154，这 5 个数就依次存进 heights[0] 到 heights[4]。

第二步，从小到大排序。 sort(heights, heights + n) 会把数组从下标 0 到 n-1 从小到大排好，得到 126 126 137 154 168。

第三步，倒序输出。 从数组的最后一个元素 heights[n-1] 开始，一步步走到第一个元素 heights[0]，输出的顺序正好是从高到矮：168 154 137 126 126。

第四步，注意格式。 每个数字之间用空格隔开，最后一个数字后面不能有多余空格。用 if (i > 0) 判断：除了第一个输出的数，其余每个数前面都先输出一个空格，最后统一换行。

想一想为什么可以"先升序再倒序"。 排序只改变顺序、不改变数据本身。把身高从小到大排好，反过来读就是从小到大的逆序，正好是从大到小，一步都不用多算。好比把 5 个人按个子从矮到高排成一列，再让队伍原地向后转，看到的顺序就是个子从高到矮了。

边界情况： n 最大 1000，数组开 heights[1005] 保证不越界；如果 n 个身高完全相同，排序后倒序输出还是一样，不影响正确性；身高范围 110~190，用 int 存放绰绰有余。

参考代码

// P4681 身高排序：把n个身高从高到低排序并输出
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    int heights[1005];
    for (int i = 0; i < n; i++) cin >> heights[i];
    sort(heights, heights + n); // 先从小到大排序
    for (int i = n - 1; i >= 0; i--) { // 倒序输出，就是从高到低
        cout << heights[i];
        if (i > 0) cout << " ";
    }
    cout << endl;
    return 0;
}

复杂度分析

sort() 的时间复杂度是 O(n log n)，n 最大 1000，排序非常快。倒序输出是一趟 O(n) 的循环。总时间复杂度 O(n log n)。空间上用一个长度为 n 的数组存身高，空间复杂度 O(n)。