希尔排序算法

希尔排序算法是插入排序的一种变种。只是这种算法，增加了一些随机因素。插入排序是整个数据是一组进行排序。希尔排序是把数据进行分组，进行排序，逐步减少组的数量，最后是一组，再进行一趟希尔排序。

希尔排序的关键点

• 本质上还是插入排序。
• 分组进行插入排序，按一定的间隔取数据组成一组，缩小间隔，组的数量步骤减少，最后形成一组进行插入排序。

举例说一下希尔排序， 以 6, 7, 4, 3, 8 为例

1. 间隔 gap = 2 (数组长度除以2)得到， 6, 7, 4, 3, 8；分成三组（6,4）（7,3），（8）

2. 三组数据进行插入排序得到，4, 7, 6, 3, 8

3 . 缩小间隔 gap = gap / 2 = 1 , 这个时候就是一组数据（4, 7, 6, 3, 8）进行插入排序

以下是python代码实现的希尔排序

def shell_sort(elements):
    n = len(elements)
    gap = int(n / 2)
    while gap > 0:
        print(gap)
        insert_sort(elements, gap)
        gap = int(gap / 2)

def insert_sort(elements, gap):
    n = len(elements)
    for i in range(gap, n, gap):
        tmp = elements[i]
        k = i
        for j in range(i - gap, -1, -gap):
            if tmp < elements[j]:
                elements[j + gap] = elements[j]
                k = j
        if k != i:
            elements[k] = tmp

if __name__ == '__main__':
    arr = [6, 7, 4, 3, 8]
    shell_sort(arr)
    print(arr)

复制

运行结果如下：

[3, 4, 6, 7, 8]