难度：入门。题目原型为洛谷 U244852 插入排序。本题的考点是插入排序的标准模板：把每个新元素插入到前面已排好序的区间，最终得到有序序列。

目标

完成本题后，你应该能够：

• 独立写出插入排序的完整代码（外层循环 + 内层「找位置并右移」）；
• 说明插入排序为什么是稳定的，以及最好/最坏情况的时间复杂度；
• 说出插入排序适合什么规模、什么形态的数据。

前置知识

• 10.1 排序的基本概念；
• 数组的下标移动与「边找边右移」的写法。

题目

读入一个整数 n 和 n 个整数，用插入排序把它们从小到大排序，并在一行内输出排序后的序列。

输入格式

• 第一行一个整数 n；
• 第二行 n 个整数，表示待排序的序列。

输出格式

一行 n 个整数，为从小到大排序后的序列，相邻整数用一个空格分隔。

数据范围

项目	范围
序列长度 n	1 ≤ n ≤ 10⁴
元素值	−10⁹ ≤ a[i] ≤ 10⁹

样例

样例输入

5
3 1 4 1 5

样例输出

1 1 3 4 5

样例解释

对 3 1 4 1 5 做插入排序：先把 1 插到 3 前得到 1 3 4 1 5，4 不动，再把第二个 1 插到最前得到 1 1 3 4 5，5 不动，最终为 1 1 3 4 5。

如何验证

先安装 Node.js、pnpm 和支持 C++17 的编译器。

# 已进入本 Lab 目录
make doctor
make run
make run CASE=001-sample
make interactive
make score

Windows 没有安装 Make 时，在仓库根目录使用等价的 pnpm 入口：

pnpm lab:run -- labs/chapter-10/exercise/E-10-03-insertion-sort-template
pnpm lab:score -- labs/chapter-10/exercise/E-10-03-insertion-sort-template

标准输出参与判题，调试信息请写入标准错误。

完成清单

• 样例输出与题目一致
• 升序、降序、含重复值、n=1 四种情况都通过
• 能说出内层 while 里 a[j] > key 为什么用 > 而不是 >=

思考题

1. 插入排序的最坏情况发生在什么输入上？此时做了多少次比较？
2. 为什么内层用 a[j] > key 时排序是稳定的？改成 a[j] >= key 会怎样？

题解

点击查看题解

思路

插入排序把数组看成「已排序前缀」和「未排序后缀」：

• 外层 for (i = 1; i < n; i++) 依次取 key = a[i]；
• 内层从 i - 1 向左，把比 key 大的元素逐个右移一位，直到找到 key 的插入位置；
• 把 key 放进去，前缀长度加一。

用 > 比较保证相等元素不交换，因此排序稳定。

复杂度分析

• 时间复杂度：最好（已有序）O(n)，最坏（逆序）O(n²)；
• 空间复杂度：O(1)（原地排序）。