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

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

　　希尔排序最开始将列表按照一定的步长（即增量）分成多个子序列，多每个子序列进行插入排序；

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

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

 

标签：

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