希尔排序(Shell Sort)也是插入类排序的一种，因DL.Shell提出而得名，因为直接插入排序每次只能移动一位，效率因此大打折扣，而且直接诶插入排序在元素有序时效率最高，希尔排序针对这一特点做了改进。

希尔排序的核心思想是将元素序列按照下标增量分割成几个子序列，对这几个子序列分别进行直接插入排序，完成一趟排序后使得元素序列变得相对有序，于是对分组使用直接插入排序的效率变高，再逐渐减小增量值重复前面的操作，这样便提高了整体的排序效率。

用Python3的方法很简单实现，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def shell_sort(lists):
    """希尔排序"""
    gap = len(lists) // 2
    while gap > 0:
        for i in range(gap, len(lists)):
            temp = lists[i]
            j = i - gap

            while j >= 0 and lists[j] > temp:
                lists[j + gap] = lists[j]
                j -= gap
            lists[j + gap] = temp
        gap //= 2
    return lists

可以看出，这里使用的初始步长为元素列表的一半，将列表分为两组后，分别进行了直接插入排序，然后在将步长折半，重复操作直到步长为1。其实也可以有另外的更高效的步长选择，这在希尔排序的维基百科上有相关讨论。

随机生成10000个数测试一下，结果如下图所示：

结果显示，希尔排序相比直接插入排序，效率大大提高了。

希尔排序的时间复杂度为O(Nlog2N)，而且是不稳定的排序，因为它在不断的分组交换过程中，可能会改变已有相同值的顺序。