数据结构与算法（希尔排序）

希尔排序

希尔排序是插入排序的一种，也称缩小增量排序，是直接插入排序算法的一种高效改进版本。希尔排序是非稳定排序算法。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至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语言描述