2947 - 打牌

题目描述

春节来临,你和朋友们一起玩起了扑克牌。

每次抓起一张牌,你会按从小到大的顺序,将这张扑克牌,插入到正确的位置,使得牌面保持从小到大的顺序。

具体抓牌时,你会先把这张牌放到最后一张牌的右侧,然后观察牌面顺序是否满足从小到大的顺序。如果不满足,再将这张牌插入到正确的位置上,使得所有的牌面保持从小到大的顺序。

这让你不禁想起了编程课上学习的插入排序。于是你的脑袋中不自觉的演练起了插入排序的过程。

假设有 5 个互不相等的整数:3 1 5 4 2。如果前 4 个数已经通过插入排序排好序了。

那么,插入 2 的过程将会是这样的:

  1. 初始状态下,先把 2 放到末尾,得到:1 3 4 5 2

  2. 2 存入临时变量 t 中。

  3. 用指针 j 指向 2 的前一个元素 5,然后判断 ta[j] 的大小关系,以决定 a[j] 是否需要后移。如果 a[j] > t,则需要让 a[j] 后移到 a[j+1] 的位置,从而得到 1 3 4 5 5

  4. 接下来,将指针 j 继续前移,判断 a[j]>t 成立,因此将 a[j] 后移到 a[j+1] 的位置,得到 1 3 4 4 5

  5. 继续将指针 j 前移,判断 a[j]>t 成立,因此将 a[j] 后移到 a[j+1] 的位置,得到 1 3 3 4 5

  6. 继续将指针 j 前移,判断 a[j]>t 不成立,因此将 t 放到 a[j+1] 的位置,得到 1 2 3 4 5

完美的插入排序的过程!

现在输入 N互不相等的整数,请编程模拟插入排序的全过程。你可以通过样例 1 的输出,更加形象的了解插入排序的过程。

请注意输出格式,除了每个元素刚插入时输出 Insert element[i]: 以外,其余每行输出前,请先输出 2 个空格。

输入

第一行输入一个正整数 N,表示读入数据的总数。

第二行输入 N 个互不相等的整数,以空格隔开。

输出

输出格式请参照样例 1 的输出格式。

样例

输入

5
3 1 5 4 2

输出

Insert element[1]:
  Init:3
  Final:3
Insert element[2]:
  Init:3 1
  Move back:3 3
  Final:1 3
Insert element[3]:
  Init:1 3 5
  Final:1 3 5
Insert element[4]:
  Init:1 3 5 4
  Move back:1 3 5 5
  Final:1 3 4 5
Insert element[5]:
  Init:1 3 4 5 2
  Move back:1 3 4 5 5
  Move back:1 3 4 4 5
  Move back:1 3 3 4 5
  Final:1 2 3 4 5

输入

4
4 3 2 1

输出

Insert element[1]:
  Init:4
  Final:4
Insert element[2]:
  Init:4 3
  Move back:4 4
  Final:3 4
Insert element[3]:
  Init:3 4 2
  Move back:3 4 4
  Move back:3 3 4
  Final:2 3 4
Insert element[4]:
  Init:2 3 4 1
  Move back:2 3 4 4
  Move back:2 3 3 4
  Move back:2 2 3 4
  Final:1 2 3 4
说明

数据规模和约定

对于 100\% 的数据,满足 N \le 100,整数元素在 int 范围。

标签
题目参数
时间限制 1 秒
内存限制 256 MB
提交次数 0
通过人数 0
金币数量 1 枚
难度 基础


上一题 下一题