首页 / 题库

P12078 - 插入排序

算法入门
通过次数1 提交次数1 内存限制 256MB 时间限制1秒

描述

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

给定一个包含 $ 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 $

意见反馈

    最多上传3张图片,格式为JPG、PNG、JPEG,单张不超过5MB

    注册

    发送验证码

    密码必须包含数字、字母和特殊字符

    找回密码

    发送验证码

    密码必须包含数字、字母和特殊字符

    运行 ID:67149

    • 测试点1:Accepted
    • 用时:0 ms
    • 内存:288 kb
    • 测试点2:Accepted
    • 用时:0 ms
    • 内存:288 kb
    输入
    203
    输出
    203

    test

    测评信息

    错误.in文件下载

    错误.out文件下载

    运行 ID:67149

    2019-01-24 15:06:36