希尔排序: （Shell Sort）是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止

时间复杂度 O(n²)

空间复杂度 O(1)

def insert_sort_gap(li, gap):
    """
    希尔排序  最坏情况 O(n²) 平均情况小于 O(n²)
    :param li:
    :param gap:
    :return:
    """
    for i in range(gap, len(li)):
        tmp = li[i]
        j = i - gap
        while j >= 0 and li[j] > tmp:
            li[j + gap] = li[j]
            j -= gap
        li[j + gap] = tmp


def shell_sort(li):
    d = len(li) // 2
    while d >= 1:
        insert_sort_gap(li, d)
        d //= 2


import random

li = [random.randint(1, 1000) for _ in range(100)]
print(li)
shell_sort(li)
print(li)