【学习笔记】希尔排序

来自b站视频

算法原理

希尔排序是插入排序的改进版。比较时不是以1为步长，而是以gap为步长。
把序列按下表的一定增量（gap）分组，对每组使用直接插入排序算法排序；随着增量gap的减小，减值1时全部序列被分为1组，算法终止。

需要三层循环。
第一层循环（gap）：gap变化最小值为1之前插入算法执行的次数
第二层循环（j）：控制的是子序列当中执行特定的插入算法的比较和交换
第三层循环（i）：控制的是所有子序列中的所有元素

如图所示

具体实现

def shellsort(alist):
   '''希尔排序'''
   n = len(alist)
   gap = n // 2 # 步长
   while gap >= 1:
       # 插入算法，与普通插入算法的区别就在于gap
       for j in range(gap, n):
           # j = [gap, gap+1, gap+2, gap+3, ... , n-1]
           i = j
           while i > 0:
               if alist[i] < alist[i-gap]:
                   alist[i], alist[i-gap] = alist[i-gap], alist[i]
                   i -= gap
               else:
                   break
       # gap缩短
       gap //= 2

测试

if __name__ == '__main__':
    li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print('原序列：', li)
    shellsort(li)
    print('排序后：', li)

结果

原序列： [54, 26, 93, 17, 77, 31, 44, 55, 20]
排序后： [17, 20, 26, 31, 44, 54, 55, 77, 93]

时间复杂度

最坏时间复杂度：O(n^2) (当gap=1时，即为插入排序)
最优时间复杂度：O(n^1.3) (根据数学策略调整出最优的gap)
稳定性：不稳定*（相同的数可能会被拆分到两部分里）*