问题 2849. -- 希尔增量排序 shell [2*]

2849: 希尔增量排序 shell [2*]

时间限制: 1 Sec  内存限制: 128 MB
献花: 11  解决: 8
[献花][花圈]

题目描述

希尔排序又称为“缩小增量(间隔)排序”。是1959年由D.L.Shell提出来的
【排序思想:】先选取一个整数d(称之为步长或间距),然后对数据进行分组。
a[1+0*d]、 a[1+1*d]、 a[1+2*d]、 …… 第1组数据
a[2+0*d]、 a[2+1*d]、 a[2+2*d]、 …… 第2组数据
……
a[d-1+0*d ]、 a[d-1+1*d]、 a[d-1+2*d]、 …… 第d-1组数据
分别对每组数据进排序,可选冒泡或插入排序。因为每组数据量少,排序速度提高。
将d值缩小,重复上述的分组和排序,直到d=1最后一次分组排序。
每次d的选择可以取 d = d div 2。第一次d=n div 2
【输入】
第一行数字n 代表接下来有n个整数
接下来n行,每行一个整数

【输出】
升序输出排序结果
每行一个数据

【样例输入】
5
12
18
14
13
16

【样例输出】
12
13
14
16
18

【数据规模】
n<=5000
每个数据<=5000

输入

输出

提示

来源

[献花][花圈]