希尔排序
希尔排序是插入排序的一种，也称缩小增量排序，是直接插入排序算法的一种高效改进版本。希尔排序是非稳定排序算法。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法终止。
希尔排序过程
希尔排序的基本思想是：将数组列在一个表中并对列分别进行插入排序，重复这个过程，不过每次用更长的列（步长更长，列数更少）来进行。最后整个表就只有一列，将数组转换至表是为了更好地理解这个算法。算法本身还是使用数组进行排序。
例：
有一个数组[1,13,5,2,6,14,9,7,8,10,15,12,16,3,4,11],如果我们以步长为5开始进行排序，我们可以通过这列表放在有5列的表中来描述算法，这样可以得到类似如下结果：(竖着的元素是步长组成)
1,13,5,2,6
14,9,7,8,10
15,12,16,3,4
11
然后对每列进行排序
1,9,5,2,4
11,12,7,3,6
14,13,16,8,10
15
将上述四行数字，依次拼接到一起得到：[1,9,5,2,4,11,12,7,3,6,14,13,16,8,10,15]，然后再以步长3进行排序：
1,9,5
2,4,11
12,7,3
6,14,13
16,8,10
15
排序之后变为：
1，4，3
2，7，5
6,8,10
12，9，11
15,14,13
16
形成序列为[1,4,3,2,7,5,6,8,10,12,9,11,15,14,13,16],之后按照以1为步长进行排序（插入排序）
希尔排序分析
shellsort.png
代码
#coding:utf-8
def shell_sort(list):
n=len(list)
#初始步长
gap=n//2
while gap>0:
#按步长进行插入排序
for i in range(gap,n):
j=i
#插入排序
while j>=gap and list[j-gap]>list[j]:
list[j-gap],list[j]=list[j],list[j-gap]
j-=gap
gap=gap//2
list=[12,56,23,64,95,1,3,7,6,8,45,56]
print(list)
shell_sort(list)
print(list)
时间复杂度
- 最优时间复杂度：根据步长序列的不同而不同
- 最坏时间复杂度：O（n^2）
- 稳定性：不稳定
参考：数据结构与算法Python语言描述
