# 希尔排序基于插入排序
def insert_sort_gap_(li,gap):
    for i in range(gap,len(li)):    # i 代表摸到的牌的下标
        tmp = li[i]
        j = i-gap        # j指的是手中的牌的下标
        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
li = list(range(1000))
import random
random.shuffle(li)
shell_sort(li)
print(li)