春节来临,你和朋友们一起玩起了扑克牌。
每次抓起一张牌,你会按从小到大的顺序,将这张扑克牌,插入到正确的位置,使得牌面保持从小到大的顺序。
具体抓牌时,你会先把这张牌放到最后一张牌的右侧,然后观察牌面顺序是否满足从小到大的顺序。如果不满足,再将这张牌插入到正确的位置上,使得所有的牌面保持从小到大的顺序。
这让你不禁想起了编程课上学习的插入排序。于是你的脑袋中不自觉的演练起了插入排序的过程。
假设有 5 个互不相等的整数:3 1 5 4 2。如果前 4 个数已经通过插入排序排好序了。
那么,插入 2 的过程将会是这样的:
初始状态下,先把 2 放到末尾,得到:1 3 4 5 2。
将 2 存入临时变量 t 中。
用指针 j 指向 2 的前一个元素 5,然后判断 t 和 a[j] 的大小关系,以决定 a[j] 是否需要后移。如果 a[j] > t,则需要让 a[j] 后移到 a[j+1] 的位置,从而得到 1 3 4 5 5。
接下来,将指针 j 继续前移,判断 a[j]>t 成立,因此将 a[j] 后移到 a[j+1] 的位置,得到 1 3 4 4 5。
继续将指针 j 前移,判断 a[j]>t 成立,因此将 a[j] 后移到 a[j+1] 的位置,得到 1 3 3 4 5。
继续将指针 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 范围。