本文共 3681 字，大约阅读时间需要 12 分钟。

希尔排序是插入排序的一个优化，如果对插入排序还有点模糊的同学，可以移步另一篇博文里面：

1.希尔排序相比插入排序，哪些地方可以优化？

• 插入排序的做法是，最外层循环控制开始从第几个元素开始笔记，例如i
• 内部循环是，从上面的i元素开始，往前面比较。如果list[i] < list[i-1]就调换顺序
• 在最坏的情况，每次比较两个元素，每次都需要调换顺序，那肯定效率就会慢很多
• 如果我们选择的列表，是相对有序一些的。即比较的次数虽然没变，但是需要调换位置的次数如果能降低很多，也可以节省效率。
• 核心：计算机的计算是非常快的，但是调换元素的位置，涉及到内存的开销，相对会慢一些。所以我们尽可能降低调换顺序，多选用计算的方式。

2.希尔排序—分步图解优化的方案

让数据列表相对更有序一些，可以用间隔的方式：

• 每次使用间隔减半的方式分组，然后再对每组进行比较，就可以达到相对有序的程度
• 即gap = n // 2

原始的数据如下：

第一次分组，分了四组时候的情况：

• 每个虚线方框算一组，共计四组
• 从索引为4的元素开始，每次与前面那个相差gap的元素比较，即索引4---->索引0比较，索引5----->索引1比较
• 如果前面的元素大，则每组中的两个元素调换位置

比较完之后，发现第2组和第4组需要调换位置

最终看到的数组，虽然整体没什么改观，但还可以继续往下分组排序：

上次gap = n// 2 ， gap = 4，分了4组，继续使用gap = gap//2 分组，得到gap = 2，分2组，分组情况如下：

• 第1次循环，从第2个（此时的gap数）索引开始，与前面间隔gap=2的数比较，2-2 = 0，所以前面能比较的只有索引为0的数
• 同理，第2次循环是，索引3与索引1比较
• 第3次循环的时候，索引4，与前面索引2比较，然后索引2与索引0再比较。两两比较，依次往前推进
• 第4次同理直到i+gap数，与i数比较完毕，次数i为0。（这个过程其实是插入排序）

最终比较完的结果为：

通过如上发现，看着还挺有序的，已经有效果了,此时，我们再进行插入排序，效率就杠杠的了！

3.分拆希尔排序------一次分组的排序

my_list = [5, 9, 1, 11, 6, 7, 2, 4]gap = 4n = len(my_list)for i in range(gap, n):    print("----------%d------------" % i)    while my_list[i - gap] > my_list[i] and i >= gap:			# 注意，此处为i最小值为gap        my_list[i - gap], my_list[i] = my_list[i], my_list[i - gap]        print("-->", my_list, "-->", i)        i = i - gap												# 每次比较的时候，向前移动gap位置    print( my_list)

----------4------------					# 这里的值，就是我们说的最外层的循环，每次从哪个索引开始，一个一个往前面比较[5, 9, 1, 11, 6, 7, 2, 4]----------5--------------> [5, 7, 1, 11, 6, 9, 2, 4] --> 5		# 带-->箭头的，说明有元素相互替换了[5, 7, 1, 11, 6, 9, 2, 4]----------6------------[5, 7, 1, 11, 6, 9, 2, 4]----------7--------------> [5, 7, 1, 4, 6, 9, 2, 11] --> 7[5, 7, 1, 4, 6, 9, 2, 11]

以上代码，如果对比着插入排序的分拆代码看，会简单很多的，插入排序一定要先搞清楚再研究这个希尔排序！！！

4.分拆希尔排序—完整代码

my_list = [5, 9, 1, 11, 6, 7, 2, 4]n = len(my_list)gap = n // 2while gap >= 1:    print("=====gap is :%d=========" % gap)    for i in range(gap, n):        print("----------%d------------" % i)        while my_list[i - gap] > my_list[i] and i >= gap:            my_list[i - gap], my_list[i] = my_list[i], my_list[i - gap]            print("-->", my_list, "-->", i)            i = i - gap        print(my_list)    gap = gap // 2

=====gap is :4=========----------4------------[5, 9, 1, 11, 6, 7, 2, 4]----------5--------------> [5, 7, 1, 11, 6, 9, 2, 4] --> 5[5, 7, 1, 11, 6, 9, 2, 4]----------6------------[5, 7, 1, 11, 6, 9, 2, 4]----------7--------------> [5, 7, 1, 4, 6, 9, 2, 11] --> 7[5, 7, 1, 4, 6, 9, 2, 11]=====gap is :2=========----------2--------------> [1, 7, 5, 4, 6, 9, 2, 11] --> 2[1, 7, 5, 4, 6, 9, 2, 11]----------3--------------> [1, 4, 5, 7, 6, 9, 2, 11] --> 3[1, 4, 5, 7, 6, 9, 2, 11]----------4------------[1, 4, 5, 7, 6, 9, 2, 11]----------5------------[1, 4, 5, 7, 6, 9, 2, 11]----------6--------------> [1, 4, 5, 7, 2, 9, 6, 11] --> 6--> [1, 4, 2, 7, 5, 9, 6, 11] --> 4[1, 4, 2, 7, 5, 9, 6, 11]----------7------------[1, 4, 2, 7, 5, 9, 6, 11]=====gap is :1=========----------1------------[1, 4, 2, 7, 5, 9, 6, 11]----------2--------------> [1, 2, 4, 7, 5, 9, 6, 11] --> 2[1, 2, 4, 7, 5, 9, 6, 11]----------3------------[1, 2, 4, 7, 5, 9, 6, 11]----------4--------------> [1, 2, 4, 5, 7, 9, 6, 11] --> 4[1, 2, 4, 5, 7, 9, 6, 11]----------5------------[1, 2, 4, 5, 7, 9, 6, 11]----------6--------------> [1, 2, 4, 5, 7, 6, 9, 11] --> 6--> [1, 2, 4, 5, 6, 7, 9, 11] --> 5[1, 2, 4, 5, 6, 7, 9, 11]----------7------------[1, 2, 4, 5, 6, 7, 9, 11]

# 如下代码，可能会更容易理解一些，和上面其实本质一样的my_list = [5, 9, 1, 11, 6, 7, 2, 4]n = len(my_list)gap = n // 2while gap >= 1:    for i in range(gap, n):        while i >= gap:            if my_list[i - gap] > my_list[i]:                my_list[i - gap], my_list[i] = my_list[i], my_list[i - gap]            i = i - gap    gap = gap // 2

以上内容有哪里不太容易看懂的，可以留言说明，我争取不断优化！

转载地址：http://iteab.baihongyu.com/