数据结构与算法 | 希尔排序

标签: 希尔排序

1 什么叫希尔排序?

  • 希尔排序(Shell Sort)是插入排序的一种。该方法因DL.Shell于1959年提出而得名。
  • 希尔排序的基本思想是:对列表数据选定一个初始gap,然后依次挑出数来,分为了几组,然后对每一组的数据进行插入排序,再将将数据归并起来,减少gap,重复上述过程,直至gap=1,此时做最后一次循环然后停止!
  • 图解:
    在这里插入图片描述

2 代码实现

思路:

  • 选定gap 然后依次挑出数来 分为了几组 然后对每一组的数据进行插入排序
  • 将数据归并起来,然后用更小的gap进行分割数据,对每一组数据再进行插入排序
  • 将数据再次归并,如果每组数据都不再发生变化 那么整体就已经排序ok

按照上述思路不是很好写代码,代码逻辑如下:

  • 首先考虑最内存循环,即插入排序的过程,注意此时的比较的对象相差一个gap,进入循环条件即为i>0即可
  • 然后考虑如何遍历所有数据呢?考虑gap作为连接彼此!还是比较难想的!
  • 最外层考虑gap每次对半取!加一个while
def shell_sort(alist):
    '''希尔排序'''
    n = len(alist)
    gap = n // 2 # 对半取整
    # gap变化到0之前,一直进行插入排序!
    while gap >= 1:
    # 希尔算法与普通插入算法不同就是gap步长
        for j in range(gap, n):
            # 控制所有子序列的所有元素
            i = j
            while i > 0:
                # 控制一个子序列 然后进行插入排序 间隔是gap 之前插入排序间隔为1
                if alist[i] < alist[i-gap]: # 比较的两个相邻元素
                    alist[i], alist[i-gap] = alist[i-gap], alist[i]
                    i -= gap
                else:
                    break
        gap -= 1 # 每次循环结束后步长减一
alist = [54,26,93,17,77,31,44,55,20]
shell_sort(alist)
print(alist)
[17, 20, 26, 31, 44, 54, 55, 77, 93]

3 时间复杂度

  • 最坏时间复杂度:一开始gap=1 即等于普通的插入排序,而普通的插入排序最坏为O(n2n^2)
  • 最优时间复杂度取决于gap的值

4 稳定性

算法不稳定各个子序列是独立的,所以相同的元素可能会不保持原来的顺序!具体见下图:
在这里插入图片描述

参考

原文链接:加载失败,请重新获取