难度：基础。题目原型为 AOJ ALDS1_1_A Insertion Sort。本题的考点是按指定格式输出插入排序的中间过程：先输出初始数组，之后每完成一次外层插入就输出一行。

目标

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

• 按「读入 → 输出初始状态 → 每轮输出」的节奏组织程序；
• 把「每轮输出一次」正确地嵌在插入排序的外层循环之后；
• 处理「数字用空格分隔、行尾无多余空格」的输出细节。

前置知识

• 10.2 插入排序的外层与内层循环；
• 一维数组的遍历与打印。

题目

读入一个整数 n 和 n 个整数。先输出初始数组一行，然后每完成一次外层插入（i = 1 .. n-1）输出一次当前数组，共输出 n 行。每行的数字用一个空格分隔。

输入格式

• 第一行一个整数 n；
• 第二行 n 个整数，表示初始序列。

输出格式

n 行，每行为当前数组（初始 + 每轮插入后），数字间用一个空格分隔。

数据范围

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

样例

样例输入

6
5 2 4 6 1 3

样例输出

5 2 4 6 1 3
2 5 4 6 1 3
2 4 5 6 1 3
2 4 5 6 1 3
1 2 4 5 6 3
1 2 3 4 5 6

样例解释

第一行是初始数组；随后每行对应一次外层插入：2 插入 → 4 就位 → … → 最后 3 插入完成排序。注意第 3、4 行相同，因为轮到 4 时它已经在正确位置，不需要移动任何元素。

如何验证

先安装 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-04-insertion-sort-steps
pnpm lab:score -- labs/chapter-10/exercise/E-10-04-insertion-sort-steps

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

完成清单

• 样例输出与题目一致（注意中间两行相同）
• n=1、已有序、逆序三种情况都通过
• 能说出为什么第 3、4 行输出相同

思考题

1. 逆序输入 5 4 3 2 1 时，每一行的变化规律是什么？整个过程一共做了多少次「右移」？
2. 如果要统计「比较次数」或「交换次数」，应该把计数器加在代码的哪一行？

题解

点击查看题解

思路

• 读入后先调用一次打印函数输出初始数组；
• 外层循环 i = 1 .. n-1，把 a[i] 通过内层 while 左移插入到正确位置；
• 每轮外层循环结束后立即打印一次当前数组。

复杂度分析

• 时间复杂度：排序 O(n²)，打印 n 行每行 O(n) 合计 O(n²)；
• 空间复杂度：O(1)（原地排序，不计输入数组）。