首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构|希尔排序

数据结构|希尔排序

作者头像
算法与编程之美
发布2019-07-17 17:51:13
5470
发布2019-07-17 17:51:13
举报

欢迎点击「算法与编程之美」↑关注我们!

本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列文章。

介绍

最坏时间复杂度O(n^2)

希尔排序是插入排序的一种,是直接插入排序算法的一种更高效的改进版。(学习希尔排序之前需要了解插入排序)。

插入排序是每次向右移动一个步长的距离,对当前数值进行操作。而希尔排序就是加大插入排序的步长,这样可以使得元素可以一次性的朝最终位置前进一大步。

举例

给出一个无序列表(下图),假设希尔排序的gap(间隔/步长)为4,可以得到四个子序列,下标为0、4、8的序列1,下标为1、5的序列2,下标为2、6的序列3、下标为3、7的序列4。

之后对每个子序列进行插入排序

如对序列1进行插入排序,将78与53比较,再将21先78做比较、再与53做比较,得到排序后的序列:21、53、78。

对所有子序列进行插入排序后再重组得到下图

之后将步长缩小为2,重复上述操作,当步长为1时的操作结束后停止,就可以得到一个有序序列。

问题解答

可能很多人刚开始接触时,会觉得这样会使插入算法变得更复杂,好像执行的步骤增加了。不是这样,虽然希尔排序的最坏时间复杂度与插入算法相同,但希尔排序的最优时间复杂度是根据步长序列的不同而不同的,最好的情况下,时间复杂度可以降到O(n^1.3)。

那这个步长怎么取呢?这个难题至今没有解答,但经过大量的实验,人们还是积累了一定的经验。

在希尔的原稿中建议的初始步长是N/2,就是是将每一次排序分成两半,虽然这样取步长在大多数情况下仍然比插入排序好,但也算不上较好,网上可以搜出很多取法,感兴趣的可以搜来看看。这里我们就以希尔原稿中的步长来讲解。

代码实现

灰线左边是不需要移动的值,右边的值需要与左边作比较,因此每次循环都需要将右边的值与左边作比较。操作顺序:78、30、43、56、21。

78的下标是4也就是步长gap,那30的下标是gap+1,43是gap+2,56是gap+3,21是gap+4。

还记得上文说的,希尔算法其实就是插入算法的改进嘛,所以我们从插入算法入手。从内往外,先写每次需要执行的比较代码。

1.先将一个子序列的灰线右边与左边做比较

2.每个子序列执行的操作相同,用一个循环控制不同序列的内部比较

3.此时一个步长所要执行的操作已结束,再用一个循环控制不同步长的操作

END

主 编 | 张祯悦

责 编 | 马原涛

where2go 团队


微信号:算法与编程之美

温馨提示:点击页面右下角“写留言”发表评论,期待您的参与!期待您的转发!

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-06-27,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 算法与编程之美 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档