希尔排序(shell sort)是插入排序的一种，也称缩小增量排序，与普通的插入算法的区别就是gap步长。
希尔排序内层循环逻辑如下所示:
上面的可以分为4组，一个一个的按照插入算法来做，第一组有54 77 20三个元素，第二组是26 31两个元素，第三组是93和44两个元素，第四组是17和55两个元素。上面的可以分为4组，一个一个的按照插入算法来做，第一组有54 77 20三个元素，第二组是26 31两个元素，第三组是93和44两个元素，第四组是17和55两个元素。
上面的按照插入算法交换后较小的数在前面，较大的数在后面。
当gap=1的时候再次执行插入算法，如下所示:
希尔排序外层循环如下所示:
代码如下所示:
# coding:utf-8def shell_sort(alist):"""希尔排序"""n=len(alist)gap = n // 2 #相除，因为涉及到/符号，所以又加了一个斜杠#print(gap) #4#gap变化到0之前，插入算法执行的次数#while gap>0:while gap >= 1:#print('gap值是',gap) #gap值是 4 gap值是 2 gap值是 1#下面的for循环是一个gap的情况，gap需求不断缩短，所以在外面又套了一层while的gap循环,上面的gap>0也可以写成gap>=1#插入算法，与普通的插入算法的区别就是gap步长#外层循环for j in range(gap,n):#j=[gap,gap+1,gap+2,gap+3,...,n-1]#print('外层循环值是',j)i = j#print('第一次',j,gap,n) #4 4 9# 先写内层循环while i>0:if alist[i] < alist[i-gap]:#print(i,gap,i-gap) #6 4 2 2 4 -2 8 4 4# print('666')# print(j,i, gap, i - gap) #6 6 4 2 6 2 4 -2 8 8 4 4 8 4 4 0alist[i],alist[i-gap] = alist[i-gap],alist[i]i-=gapelse:break#break;#break;#缩短gap步长gap //=2#print('gap除以2后的值是', gap) #gap除以2后的值是 2 gap除以2后的值是 1 gap除以2后的值是 0if __name__ == "__main__":li = [54, 26, 93, 17, 77, 31, 44, 55, 20]print(li)shell_sort(li)print(li)"""[54, 26, 93, 17, 77, 31, 44, 55, 20][17, 20, 26, 31, 44, 54, 55, 77, 93]"""
另外一种实现方式如下所示:
# 创建一个希尔排序的函数def shell_sort(alist):# 需要排序数组的个数N = len(alist)# 最初选取的步长gap = N // 2# 根据每次不同的步长，对分组内的数据进行排序# 如果步长没有减为1就继续执行#while gap > 0:while gap >= 1:# 对每个分组进行插入排序，# 因为插入排序从第二个元素开始，而这里第二个元素的下标就是gap# 所以j的起始点是gapfor j in range(gap, N): # 4 2 1这种,j的开始值是4，后来越来越小 2 1# 控制每个分组内相邻的两个元素,逻辑上相邻的两个元素间距为gap，# i的前一个元素比它少一个gap距离，所以for循环中j的步长为 -gapfor i in range(j, 0, -gap):# 判断和逻辑上的分组相邻的两个数据大小if alist[i] < alist[i - gap] and i - gap >= 0:# 交换temp = alist[i]alist[i] = alist[i - gap]alist[i - gap] = temp# 改变步长gap = gap // 2numlist = [5, 7, 8, 3, 1, 2, 4, 6, 9]print("排序前：%s" % numlist)shell_sort(numlist)print("排序后：%s" % numlist)"""排序前：[5, 7, 8, 3, 1, 2, 4, 6, 9]排序后：[1, 2, 3, 4, 5, 6, 7, 8, 9]"""
