【算法实践】手把手带你简单实现希尔排序

举报
迷彩 发表于 2023/05/29 22:28:47 2023/05/29
【摘要】 前言希尔排序是什么?希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进版本。该方法又称缩小增量排序或者递减增量排序算法,跟插入排序不一样的是希尔排序是非稳定排序算法。因D.L.Shell于1959年提出而得名。希尔排序算法实质上是一种分组插入方法。他的基本思想如下:设待排序元素序列有n个元素,选择一个增量序列 d1,d2,……,dt,其中 di > dj, dt ...

前言

希尔排序是什么?

希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进版本。该方法又称缩小增量排序或者递减增量排序算法,跟插入排序不一样的是希尔排序是非稳定排序算法。因D.L.Shell于1959年提出而得名。

希尔排序算法实质上是一种分组插入方法。他的基本思想如下:

设待排序元素序列有n个元素,选择一个增量序列 d1,d2,……,dt,其中 di > dj, dt = 1;先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序(之前写过一篇关于插入排序的文章,这里就不再赘述,需要的童鞋可点击连接了解《【算法实践】手把手带你快速实现插入排序);然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-1<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。

由于开始时,dt的取值较大,每个子序列中的元素较少,排序速度较快,到排序后期dt取值逐渐变小,子序列中元素个数逐渐增多,但由于前面工作的基础,大多数元素已经基本有序,所以排序速度仍然很快。


希尔排序是基于插入排序的以下两点性质而提出改进方法的:

  1. 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率

  2. 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位


下图是插入排序和希尔排序的对比:


希尔排序的平均时间复杂度:O(nlogn) 最好情况和最坏情况都是O(n⋅logn2),空间复杂度是O(1),是一种不稳定排序.

图解希尔排序

增量序列 d1,d2,……,dt,其中 di > dj, dt = 1

按增量序列个数 k,对序列进行 k 趟排序;

每趟排序,根据对应的增量dt,将待排序列分割成若干长度为 m 的子序列,分别对各子表进行直接插入排序。仅增量因子为 1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

如现有以下n(6)个数:排序前: [22, 23, 48, 23, 18, 7]


希尔排序中增量的取法:

增量dt的取法有各种方案。最初shell提出取dt=n/2向下取整,dt=dt/2向下取整,直到dt=1。但由于直到最后一步,在奇数位置的元素才会与偶数位置的元素进行比较,这样使用这个序列的效率会很低。后来Knuth提出取dt=n/3向下取整+1.还有人提出都取奇数为好,也有人提出dt互质为好。应用不同的序列会使希尔排序算法的性能有很大的差异


增量dt的取值方法是:(n/3的值向下取整 )+ 1

  1. 第一趟排序dt的取值为(6/3的值向下取整 )+ 1=3,即对比的数据间隔为3,分成3组


  1. 第二趟排序dt的取值为(3/3的值向下取整 )+ 1=2,即对比的数据间隔为2,一共分成2组



  1. 第三趟排序dt的取值为(2/3的值向下取整 )+ 1=1,即对比的数据间隔为1,两两比较只剩下一个分组


直到dt=1时,就是对整个数列做最后一次调整,因为前面的序列调整已经使得整个序列部分有序,所以最后一次调整也变得非常快

从上面的图示中可以看到粉红色方块的23本来在紫色方块的23前面,排序完成后,粉红色方块的23排序到紫色方块的23后面,可看出希尔排序是个不稳定的排序算法.

代码实现

导入math库,math库是Python内置的标准库,里面定义了与数学相关的函数

import math

定义排序函数shellSort():

def shellSort(arr):
    gap=1
    while(gap < len(arr)/3):
        gap = gap*3+1
    while gap > 0:
        for i in range(gap,len(arr)):
            temp = arr[i]
            j = i-gap
            while j >=0 and arr[j] > temp:
                arr[j+gap]=arr[j]
                j-=gap
            arr[j+gap] = temp
        gap = math.floor(gap/3)
    return arr


验证算法:

arrList = [22,23,48,23,18,7]
print('排序前:',arrList)

sortedArr = shellSort(arrList)

print('排序后:',sortedArr)

执行结果如下:


【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。