描述
插入排序是一种简单直观的排序算法,其工作原理类似于打牌时整理手牌的过程:每次从待排序序列中取出一个元素,将其插入到已排序序列中的正确位置,使得已排序序列始终保持有序。
给定一个包含 $ 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 $

关注我们