基本思想

设待排序序列的长度为 n，选择若干个步长 gap（1 < gap < n），并将索引的差为 gap 的整数倍的元素作为一组，然后对这些分组分别使用直接插入排序进行排序，待整个序列基本有序之后，让 gap = 1，对整个序列进行一次直接插入排序。

希尔排序的过程

其中：

第一趟排序过程中，gap = 5；

第二趟排序过程中，gap = 3；

第三趟排序过程中，gap = 1；

Python 实现

tim-chow 的 Github

时间复杂度

希尔排序的时间复杂度很难计算。根据经验，希尔排序的时间复杂度在 O(nlogn) 到 O(n²) 之间，平均时间复杂度是 O(n^1.3)

空间复杂度

O(1)