希尔排序的基本思想：希尔排序是直接插入排序的改进版，也称之为缩小增量排序。首先将整个序列分割成为若干子序列分别进行直接插入排序，等到整个序列中的记录基本有序时，再对整体序列依次进行直接插入排序。

时间复杂度：

• 最好情况O(n)
• 最坏情况O(n**2)
• 平均情况O(n**1.3)

空间复杂度:O(1)

属于不稳定的排序算法

代码:

def shell(arr):
    n = len(arr)
    mid = int(n / 2)
    while mid> 0:
        for i in range(mid, n):
            temp = arr[i]
            j = i
            while j >= mid and arr[j - mid] > temp:
                arr[j] = arr[j - mid]
                j -= mid
            arr[j] = temp
        mid = int(mid / 2)


if __name__ == '__main__':
    arr = [12, 56, 34, 4, 8, 3, 0]
    print('排序前:')
    for i in arr:
        print(i,end=' ')
    shell(arr)
    print('
排序后:')
    for i in arr:
        print(i,end=' ')

运行结果:

排序前:
12 56 34 4 8 3 0 
排序后:
0 3 4 8 12 34 56