题目描述

希尔(Shell)排序又称为缩小增量排序，它是一种插入排序。它是直接插入排序算法的一种威力加强版。

该方法因DL．Shell于1959年提出而得名。 


希尔排序的基本思想是： 


把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。

随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。

输入格式

输入一个n(n 下一行输入n个数字的序列

输出格式

对序列进行希尔排序 输出每轮排序后的结果 每组样例后又一个空行

21
46 39 76 12 94 84 91 98 26 75 87 41 84 60 57 88 72 94 83 12 21
14
28 52 65 73 66 26 62 104 31 63 52 9 86 20

21 39 76 12 57 84 72 94 26 12 46 41 84 60 94 88 91 98 83 75 87 
21 39 76 12 12 46 41 84 26 57 84 72 94 60 75 87 91 98 83 94 88 
12 12 21 39 26 46 41 57 75 60 76 72 83 84 84 87 88 94 91 98 94 
12 12 21 26 39 41 46 57 60 72 75 76 83 84 84 87 88 91 94 94 98 

28 31 63 52 9 26 20 104 52 65 73 66 86 62 
20 9 26 28 31 52 52 62 63 65 73 66 86 104 
9 20 26 28 31 52 52 62 63 65 66 73 86 104