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

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

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

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

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