首页 > 编程语言 > 详细

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

时间:2018-01-21 11:46:17      阅读:313      评论:0      收藏:0      [点我收藏+]

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

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

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

  重复上述步骤,直到步长为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)之间。

 

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

原文:https://www.cnblogs.com/jade-91/p/8323648.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!