希尔排序

希尔排序(ShellSort)是以它的发明者Donald Shell名字命名的,希尔排序是插入排序的改进版,实现简单,对于中等规模数据的性能表现还不错

排序思想

前情回顾:直接插入排序(对插入排序不熟悉的强烈建议先阅读此文)

一天,一尘拿着扑克自己在那玩,刚被师傅看见了

慧能

上次的插入排序掌握了没

恩恩,基本掌握了

一尘

慧能

那你说说插入排序什么时候使用高效?

小规模数据数据或者基本有序或者时十分高效。

一尘

数据有序程度越高,越高效(移动少)

慧能

恩恩,不错,基本有序或规模较小都不常见,你能不能改进一下插入排序,使得它对较大规模并且无序的数据也非常有效率

这个......,弟子不才

一尘

慧能

其实希尔排序就可以实现这个效果

希尔排序是怎么做的呢?

一尘

慧能

它的思路是这样的:

首先它把较大的数据集合分割成若干个小组(逻辑上分组),然后对每一个小组分别进行插入排序,此时,插入排序所作用的数据量比较小(每一个小组),插入的效率比较高

下面有颜色的是逻辑上的分组,并没有实际地进行分组操作,在数组中的位置还是原来的样子,只是将他们看成这么几个分组(逻辑上分组)

可以看出,他是按下标相隔距离为4分的组,也就是说把下标相差4的分到一组,比如这个例子中a[0]与a[4]是一组、a[1]与a[5]是一组...,这里的差值(距离)被称为增量

每个分组进行插入排序后,各个分组就变成了有序的了(整体不一定有序)

此时,整个数组变的部分有序了(有序程度可能不是很高)

然后缩小增量为上个增量的一半:2,继续划分分组,此时,每个分组元素个数多了,但是,数组变的部分有序了,插入排序效率同样比较高

同理对每个分组进行排序(插入排序),使其每个分组各自有序

最后设置增量为上一个增量的一半:1,则整个数组被分为一组,此时,整个数组已经接近有序了,插入排序效率高

同理,对这仅有的一组数据进行排序,排序完成

希尔排序真厉害啊,同时构造出两个特殊条件以达到高效插入

一尘

慧能

恩恩,这就是希尔排序的精华所在

排序代码

慧能

既然知道了思想,那你写一写代码吧

对于已经熟悉插入排序的一尘来说这并不是什么难事,很快,一尘写出了希尔排序的代码

对各个组进行插入的时候并不是先对一个组进行排序完再对另一个组进行排序,而是轮流对每个组进行插入排序

一尘

随后一尘写出了插入arr[i]到所在组正确位置的代码(insertI)

insertI和直接插入排序里的插入代码几乎完全一样

慧能

恩恩,不错,插入排序会,这个代码就简单许多,只是在外层多加了一个控制增量(gap)的循环罢了

时间复杂度

接下来又是分析时间复杂度吧,一尘心里想

慧能

这次的时间复杂度你不用分析了,你只需记住结论就行了,因为希尔排序的时间度分析极其复杂,有的增量序列的复杂度至今还没人能够证明出来

增量序列?

一尘

慧能

就是你刚才使用的增量的集合,刚才用的序列就是{1, 2, 4, ...},每次都通过减半来得到新的增量

希尔排序的复杂度和增量序列是相关的

{1,2,4,8,...}这种序列并不是很好的增量序列,使用这个增量序列的时间复杂度(最坏情形)是O(n^2)

Hibbard提出了另一个增量序列{1,3,7,...,2^k-1},这种序列的时间复杂度(最坏情形)为O(n^1.5)

Sedgewick提出了几种增量序列,其最坏情形运行时间为O(n^1.3),其中最好的一个序列是{1,5,19,41,109,...}

对不同增量的复杂度感性趣可以参考《数据结构与算法分析》一书或其他相关论文

想不到算法简单排序时间复杂度却如此困难

一尘

慧能

是啊,有的东西看起来简单,其实里面却很复杂

关于时间复杂度可看:

算法分析神器—时间复杂度

稳定性

慧能

最后说一下稳定性吧

不是稳定的,虽然插入排序是稳定的,但是希尔排序在插入的时候是跳跃性插入的,有可能破坏稳定性

一尘

原文发布于微信公众号 - 趣谈编程(gh_51e791ad9174)

原文发表时间:2018-04-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏醒者呆

面向程序员编程——精研排序算法

这篇文章很长,我花了好久的时间(中间公司出了bug,加班了好几天( ¯ ¨̯ ¯̥̥ ))进行整理,如有任何疑问,欢迎随时留言。 关键字:排序算法,时间...

40150
来自专栏HTML5学堂

算法之旅 | 快速排序法

HTML5学堂-码匠:前几期“算法之旅”跟大家分享了冒泡排序法和选择排序法,它们都属于时间复杂度为O(n^2)的“慢”排序。今天跟大家分享多种排序算法里使用较广...

35950
来自专栏PPV课数据科学社区

【学习】视觉直观感受 7 种常用排序算法

10月14日发布《统计世界的十大算法》后,很多朋友在后台询问,哪里有“视觉直观感受 7 种常用排序算法”,今天分享给大家,感谢todayx.org。 1. 快速...

32550
来自专栏Crossin的编程教室

【Python 第73课】reduce 函数

上次说了 Python 中一个比较有意思的内置函数 map,今天再来介绍另一个类似的函数:reduce map 可以看作是把一个序列根据某种规则,映射到另一个序...

29360
来自专栏Python爬虫与算法进阶

学点算法之字符串的乱序检查

问题 字符串的乱序检查。 一个字符串是另一个字符串的乱序。如果第二个字符串只是第一个的重新排列,例如,’heart’ 和 ‘earth’ 就是乱序字符串。’py...

41580
来自专栏蓝天

常见指针定义解读

最近做的C/C++技术面试比较多,发现了一些共同的问题,对于如下所示的指针认识,多数面试者都答错了,作为过来人,这种情况还可以理解的,放在一起确实有些复杂。 ...

5610
来自专栏轮子工厂

八大排序算法稳定性分析,原来稳定性是这个意思...

2、在一趟选择中,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了;

27360
来自专栏Crossin的编程教室

【Python 第72课】map 函数

来看两个问题: 1. 假设有一个数列,如何把其中每一个元素都翻倍? 2. 假设有两个数列,如何求和? 第一个问题,普通程序员大概会这么写: lst_1 = [...

323100
来自专栏云霄雨霁

排序算法总结

13800
来自专栏java一日一条

面试中的 10 大排序算法总结

查找和排序算法是算法的入门知识,其经典思想可以用于很多算法当中。因为其实现代码较短,应用较常见。所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗,只...

22330

扫码关注云+社区

领取腾讯云代金券