python算法与数据结构-希尔排序算法

﹏ヽ暗。殇╰゛Y 2023-10-06 12:53 16阅读 0赞

希尔排序(shell sort)是插入排序的一种，也称缩小增量排序，与普通的插入算法的区别就是gap步长。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70][]

希尔排序内层循环逻辑如下所示:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 3][]

上面的可以分为4组，一个一个的按照插入算法来做，第一组有54 77 20三个元素，第二组是26 31两个元素，第三组是93和44两个元素，第四组是17和55两个元素。上面的可以分为4组，一个一个的按照插入算法来做，第一组有54 77 20三个元素，第二组是26 31两个元素，第三组是93和44两个元素，第四组是17和55两个元素。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 4][]

上面的按照插入算法交换后较小的数在前面，较大的数在后面。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 5][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 6][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 7][]

当gap=1的时候再次执行插入算法，如下所示:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 8][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 9][]

希尔排序外层循环如下所示:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 10][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 11][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 12][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 13][]

代码如下所示:

# coding:utf-8
    def 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 0
                          alist[i],alist[i-gap] = alist[i-gap],alist[i]
                          i-=gap
                      else:
                          break
                  #break;
              #break;
              #缩短gap步长
              gap //=2
              #print('gap除以2后的值是', gap) #gap除以2后的值是 2 gap除以2后的值是 1 gap除以2后的值是 0
    
    
    if __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的起始点是gap
            for j in range(gap, N): # 4 2 1这种,j的开始值是4，后来越来越小  2 1
                # 控制每个分组内相邻的两个元素,逻辑上相邻的两个元素间距为gap，
                # i的前一个元素比它少一个gap距离，所以for循环中j的步长为 -gap
                for 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 // 2
    
    
    numlist = [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]
    """

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200712182915377.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/202007121829504.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200712183038679.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200712183114477.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200712183213873.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200712183245209.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200712183321546.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200712183402667.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200712183425358.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200712183537609.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20200712183624773.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/20200712183644447.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 12]: https://img-blog.csdnimg.cn/20200712183720547.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 13]: https://img-blog.csdnimg.cn/2020071218374364.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70