算法实战-OC希尔排序(二)

我没有为这种算法做任何事,我的名字不应该出现在算法的名字中。---- 希尔(shell排序作者)

希尔排序按其设计者希尔(Donald Shell)的名字命名,该算法由1959年公布。一些老版本教科书和参考手册把该算法命名为Shell-Metzner,即包含Marlene Metzner Norton的名字,但是根据Metzner本人的说法,“我没有为这种算法做任何事,我的名字不应该出现在算法的名字中。”

----那时候的名人多谦虚.

第一.定义

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

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

第二: 插入排序

既然提到了插入排序, 就在此先了解一下插入排序; 它的是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

话说一图胜千言, 来一张个人认为最容易理解的图:

来自维基百科--插入排序

对上图解释一下:

直接上OC代码, 之后会随着希尔排序一块放在github上:

第三. 分析

还是说产生的缘由吧,

主要是和时间复杂度O(n²)过不去, 就是看你不顺眼.

聊天都离不开GIF, 这里怎么能少!隔着GIF图就感觉到前辈们的牛逼气息!

希尔排序通过将比较的全部元素来提升插入排序的性能。即: 可以将数据放在一个,每个区一列, 然后对每一列排序.

待排序数组---[9, 1, 5, 8, 3, 7, 4, 6, 2], 先将,稍后看步长

例子一

第一次原始数据为[9, 1, 5, 8, 3, 7, 4, 6, 2]

第一次后为[4, 1, 2, 8, 3, 5, 9, 6, 7];

第二次原始数据为[4, 1, 2, 8, 3, 5, 9, 6, 7];

第二次后为[2, 1, 3, 5, 4, 6, 7, 8, 9];

第三次步长==1, 排序后为[1, 2, 3, 4, 5, 6, 7, 8, 9]

例子二

以图片的形式展示以上的操作步骤:

重点---步长计算

通过以上的与希尔排序的例子, 想必对希尔排序有了初步的认识, 但对于步长这个东西完全模糊....放心;

因为步长的选择是希尔排序的重要部分, 所以摘出来单独说明; 作者最初的建议是折半再折半知道最后的步长为1, 但是, 如果一个数列以步长5进行了排序然后再以步长3进行排序,那么该数列不仅是以步长3有序,而且是以步长5有序。如果不是这样,那么算法在迭代过程中会打乱以前的顺序,那就不会以如此短的时间完成排序了。 摘录自wiki百科

已知的最好步长序列是由提出的 **1,5,19,41,109,... **

它是由交错两个序列的元素获得:

这项研究也表明用这样步长序列的希尔排序比,甚至在,但是在涉及希尔排序还是。可以参考 Sorting Algorithms - Shellsort

OC希尔排序代码

还得在整理一下.....

参考链接

1. 维基百科

2. Sorting Algorithms - Shellsort

  • 发表于:
  • 原文链接:http://kuaibao.qq.com/s/20180130G10BJE00?refer=cp_1026

同媒体快讯

相关快讯

扫码关注云+社区