【 python 学习笔记 -- 数据结构与算法 】希尔排…

2018-06-18 00:45:11来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

【希尔排序】:也叫做递减增量排序算法,在插入排序算法的基础上做了改进。

  希尔排序最开始将列表按照一定的步长(即增量)分成多个子序列,多每个子序列进行插入排序;

  然后减小步长,重新分割子序列,再对每个子序列进行插入排序;

  重复上述步骤,直到步长为1,对整个列表进行插入排序,排序完成。

 

【示意图】

  给定一个长度n=9的列表,选择一定的步长,这里为3,将列表分成如下三个子列表(sublist 1, 2, 3)

  对每一个子列表进行插入排序,最终列表如下图所示,我们发现尽管列表没有完全正序,但是很多元素已经距离最终位置非常接近了,这也就减少了插入排序时的移动次数。

 

【 implementation of shell sort 】:

   步长的选取是希尔排序的关键。Donald Shell最初建议步长选择为n/2,其中n为列表长度,随后对步长取半直到为1。

  目前最好的步长序列是由Sedgewick提出的,为 (1,5,19,41,109...)。

  这里我只采用了Donald Shell给出的步长序列来实现希尔排序:          

  

【 performance analysis 】

  时间复杂度根据不同的步长选取而不同,最好和最坏情况也不同,处于O(n)和O(n2)之间。

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Django中模型(四)

下一篇:Django中模型(三)