希尔排序

希尔排序(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 条评论
登录 后参与评论

相关文章

来自专栏人工智能LeadAI

讨厌算法的程序员 | 第六章 归并排序

分而治之 从算法设计的分类上来说,插入排序属于增量方法。在排序好子数组A[1 ‥ j-1]后,再将单个元素A[j]插入子数组的适当位置,产生排序好的子数组A[1...

3576
来自专栏python读书笔记

《python算法教程》Day8 - 构建二分搜索树二分搜索树介绍二分搜索树创建代码

今天是《python算法教程》的第8篇读书笔记,笔记的主要内容是构建二分搜索树。 二分搜索树介绍 若要对一组有序值中执行操作(如查找),二分搜索法是一个优秀的选...

33513
来自专栏趣谈编程

外部排序

当我们要排序的文件太大以至于内存无法一次性装下的时候,这时候我们可以使用外部排序,将数据在外部存储器和内存之间来回交换,以达到排序的目的

1030
来自专栏算法channel

归并排序算法的过程图解

主要推送关于对算法的思考以及应用的消息。坚信学会如何思考一个算法比单纯地掌握100个知识点重要100倍。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎...

33611
来自专栏开源优测

Python3希尔排序

希尔排序 概述 希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminshing Increment Sort),是直接插入排序算...

33710
来自专栏PHP技术

PHP实现四种基本排序算法

许多人都说算法是程序的核心,算法的好坏决定了程序的质量。作为一个初级phper,虽然很少接触到算法方面的东西。但是对于基本的排序算法还是应该掌握的,它是程序开发...

2563
来自专栏令仔很忙

有意思的算法(一)----冒泡排序

有12,35,99,18,76五个数进行从大到小的排序,既然是从大到小排序,也就是说越小的越靠后,可不要把这句当成废话,这可是最关键的地方!

711
来自专栏Java 源码分析

排序算法

选择排序: ​ 选择排序一般来说就是,我们 始终从中右边的序列中找出那些最小的元素,放在左侧,这样我们就能保证左边始终有序。 ​ 但是这个算法的复杂...

3356
来自专栏TensorFlow从0到N

讨厌算法的程序员 6 - 归并排序

? 分而治之 分而治之 从算法设计的分类上来说,插入排序属于增量方法。在排序好子数组A[1 ‥ j-1]后,再将单个元素A[j]插入子数组的适当位置,产生排序...

2464
来自专栏向治洪

算法之插入排序

插入排序算法介绍 排序算法是最简单的算法,也是最基本的算法。顾名思义,插入排序就是把当前待排序的元素插入到一个已经排好序的列表里面。 一个非常形象的例子就是右手...

1979

扫码关注云+社区