12078 - 插入排序

插入排序是一种简单直观的排序算法，其工作原理类似于打牌时整理手牌的过程：每次从待排序序列中取出一个元素，将其插入到已排序序列中的正确位置，使得已排序序列始终保持有序。

给定一个包含 n 个整数的数组，请模拟插入排序的完整过程，并按照指定格式输出每一步的序列状态。

算法步骤（以数组 3 1 5 4 2 为例）

1. 初始已排序序列为空。
2. 第 1 个元素 3：直接放入，序列变为 3。
3. 第 2 个元素 1：将 1 与已排序序列 3 比较，3 > 1，将 3 后移一位，序列变为 3 3，然后将 1 放入空位，得到 1 3。
4. 第 3 个元素 5：5 大于 3，无需移动，直接追加，得到 1 3 5。
5. 第 4 个元素 4：从后往前比较，5 > 4，将 5 后移，序列变为 1 3 5 5；然后 3 <= 4，停止，将 4 放入空位，得到 1 3 4 5。
6. 第 5 个元素 2：依次将 5, 4, 3 后移，最后将 2 插入，得到 1 2 3 4 5。

你需要输出每一步的序列变化，格式详见下文。

• 第一行包含一个正整数 n （ 1 \le n \le 100 ），表示数组元素的个数。
• 第二行包含 n 个整数，表示待排序的数组元素，整数之间用空格隔开。

输出共分为 n 个部分，每个部分对应一个元素的插入过程，格式如下：

1. 每个部分以 Insert element[i]: 开头，其中 i 从 1 开始。
2. 接下来的每一行（包括 Init、Move back、Final）前必须缩进两个空格（即行首输出两个空格）。
3. 对于第 ( i ) 个元素：
   • 首先输出 Init: 后跟当前已排序序列（即前 ( i-1 ) 个元素已排序后的序列）加上第 ( i ) 个元素（位于末尾）所组成的序列。
   • 然后，执行插入排序中的后移操作：每次将一个大于当前元素的已排序元素后移一位，并输出一行 Move back: 后跟移动后的完整序列（包含当前元素的占位，即重复的最后一个元素）。重复直到找到正确位置。
   • 最后，将当前元素放入正确位置，输出一行 Final: 后跟插入完成后的完整序列。

• 对于第一个元素，没有移动操作，因此只有 Init 和 Final 两行（格式仍需要缩进两个空格）。
• 所有序列中的整数之间用一个空格隔开。

数据范围与约定

• 1 \le n \le 100
• 数组元素绝对值不超过 10^9

蓝桥杯