P4668 插入排序练习（入门）

解题思路

第一步，把要排的数放好。 读入 n 个数，存进数组 nums。我们要用插入排序把它们降序排列：从第二个数开始，把当前要插入的数记到 key 里，往前面已经排好的部分找合适的位置。

第二步，找位置并腾地方。 用一个变量 j 从 i-1 开始往左走，只要 nums[j] 比 key 小，就说明 nums[j] 得往后让位，把它往右挪一位（nums[j+1] = nums[j]），j 继续左移。注意因为要降序，比较符号是"小于"：小的数往右让，大的 key 才能往前插。

第三步，把 key 放到位。 循环停住时，key 的位置就空出来了，把 key 放到 nums[j+1]，这一轮就把一个数插到了正确的位置。

第四步，重复处理所有数。 外层循环从 i=1 走到 i=n-1，依次把每个数插好，整个数组就是降序排列的，最后输出，数之间用空格隔开，末尾换行。

想一想生活里的例子。 整理一摞从高到低排列的奖状，新拿一张要插到合适的高度位置，比它矮的奖状往下挪一挪。

边界情况： 重复数字照常处理，等于 key 的数不用挪，所以两个 9 都保留，输出 9 9 7 4 2。题目没写 n 的上限，数组开大一点（10005）更保险。

参考代码

// P4668 插入排序练习：用插入排序把 n 个正整数降序排列
#include <iostream>
int main() {
    int n, nums[10005];
    std::cin >> n;
    for (int i = 0; i < n; i++) std::cin >> nums[i];
    for (int i = 1; i < n; i++) {
        int key = nums[i], j = i - 1;
        while (j >= 0 && nums[j] < key) {   // 把比 key 小的数往后移
            nums[j + 1] = nums[j];
            j--;
        }
        nums[j + 1] = key;   // key 落到正确位置
    }
    for (int i = 0; i < n; i++) {
        if (i) std::cout << " ";
        std::cout << nums[i];
    }
    std::cout << "\n";
    return 0;
}

复杂度分析

插入排序最坏情况时间复杂度 O(n^2)，最好情况（基本有序）O(n)。题目没有给出 n 的上限，但作为"插入排序练习"，n 一般不会太大，O(n^2) 可以接受。空间复杂度 O(n)。核心要点是把比较符号写对：降序用小于号，升序用大于号，写反就变成升序了。