P4666 n个数降序排序（入门）

解题思路

第一步，读懂题目。 输入 n 个整数，要求用插入排序把它们从大到小排好。

第二步，想想生活里的例子。 打扑克牌时，我们拿到新牌会把它插到手里已经排好序的牌堆中的合适位置。插入排序就是这样：从第二个数开始，把它往前"插"，插到前面已经排好序的部分里正确的位置。

第三步，写出插入排序的步骤。 外层循环 i 从 1 到 n-1，先把 num[i] 记到 key 里，然后让 j=i-1 从右往左找位置：只要 num[j] < key，就把 num[j] 往后挪一格，继续往前看；直到找到一个不小于 key 的数，就把 key 放到 num[j+1] 的位置。因为我们要降序，所以小的数要往后挪，给大的数让位。

第四步，用例子走一遍。 假设数组是 3 1 4。i=1 时 key=1，它前面的 3 比 1 大，不用动；接着 i=2 时 key=4，前面两个数 3、1 都比 4 小，于是一个一个往后挪，腾出最前面的位置，把 4 放进去，数组变成 4 3 1，降序完成。整个过程就像把一张新牌插进手里已经排好的牌堆。

第五步，处理边界情况。 数组只有 1 个数时直接输出；最小的数会一路挪到最前面，while 循环里 j 变成 -1 时退出，然后 key 放到 num[0]。n 最大 100，数组开 105 足够。

第六步，注意输出格式。 输出时数之间用空格隔开，最后一个数后面换行。另外插入排序在数组基本有序时会非常快，因为要挪动的元素很少，这一点让它比冒泡排序更聪明一点。

参考代码

// P4666 n个数降序排序：插入排序，从第二个数开始往前插入，大的往前挪
#include <iostream>
int main() {
    int n, num[105];
    std::cin >> n;
    for (int i = 0; i < n; i++) std::cin >> num[i];
    for (int i = 1; i < n; i++) {
        int key = num[i], j = i - 1;
        while (j >= 0 && num[j] < key) {   // 比 key 小的往后挪，腾出位置
            num[j + 1] = num[j];
            j--;
        }
        num[j + 1] = key;   // 把 key 插到正确位置
    }
    for (int i = 0; i < n; i++) {
        if (i) std::cout << " ";
        std::cout << num[i];
    }
    std::cout << "\n";
    return 0;
}

复杂度分析

插入排序最坏情况（输入已经是升序、要排成降序）每次都要挪很多位，时间复杂度 O(n^2)。n 最大只有 100，最多一万次操作，完全没问题。空间上只用了一个数组，是 O(n)。插入排序虽然比快排慢，但实现简单，适合小规模数据，也是理解排序思想的好入门算法。