希尔排序就这么简单

一、希尔排序介绍

来源百度百科:

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

从上面我们很容易看出来,它是插入排序的高级版

回顾一下插入排序:

将数据插入到已有序的数列中

排序前:将每个元素看成有序的数列

第一趟排序后:得到一个有序数列,其大小为2

第二趟排序后:得到一个有序数列,其大小为3

第三趟排序后:得到一个有序数列,其大小为4

........每一趟插入排序,都可以将一个无序值插入一个有序数列,直至全部值有序

如果给出的数组足够乱的话,那么插入排序所耗费的时间是O(n^2)

既然希尔排序是插入排序的高级版,那它做了哪些优化呢??让我们来看看:

希尔排序在排序前:将一个序列分成了好几个序列

在第一趟排序时:将这几个序列做插入排序。排序后,部分较大的数字往后靠,部分较小的数字往前靠

在第二趟排序时:将这个序列又分了好几个序列做插入排序(但比第一次分的数要少,ps:如果第一次分5个,第二次可能就2个了)。排序后,部分较大的数字往后靠,部分较小的数字往前靠

................

在第n趟排序时:将这个序列又分了好几个序列(直到剩下一个序列),从宏观上看,此序列就基本是有序的了。这时就用简单插入排序将数列直至已序

从直观上看希尔排序:

就是把数列进行分组(不停使用插入排序),直至从宏观上看起来有序,最后插入排序起来就容易了(无须多次移位或交换)。

那么,上面那里说了将一个序列分成好几个序列,那么到底怎么分呢?比如有10个元素的序列,分成几个才合适?每次缩减又是多少呢?

从专业的角度上讲,将一个序列分成好几个序列,用一个数来表示:那个数称为增量。显然的是,增量是不断递减的(直到增量为1)

往往的:如果一个数列有10个元素,我们第一趟的增量是5,第二趟的增量是2,第三趟的增量是1。如果一个数列有18个严肃,我们第一趟的增量是9,第二趟的增量是4,第三趟的增量是2,第四趟的增量是1

很明显我们可以用一个序列来表示增量:

,每次增量都

/2

二、希尔排序体验

现在我们有一个数组,该数组有6个元素

int[] arrays = ;

排序前:

将该数组看成三个(arrays.length/2)数组,分别是:

,

,

第一趟排序:

对三个数组分别进行插入排序,因此我们三个数组得到的结果为

,

,

此时数组是这样子的:

第二趟排序:

增量减少了,上面增量是3,此时增量应该为1了,因此把

看成一个数组(从宏观上是有序的了),对其进行插入排序,直至有序

可能我举的例子不够好(没看到很好的效果),我们来看看网上的图片,加深一下希尔排序的过程:

PS:图片来源网上(侵删)

三、希尔排序代码实现

我们发现希尔排序代码其实非常简单(相比对堆排序),理解起来也不难,就用增量来将数组进行分隔,直到增量为1。底层干的还是插入排序干的活~

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180325A17CPT00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码关注腾讯云开发者

领取腾讯云代金券