希尔排序

概念

gap每次分半，直到最小值1
循环，下标i从 gap到n
对比下标i与i-gap的值

不稳定，最坏O(²)

示意图

代码实现

lst = [2,7,4,0,5]
def xier_sort(lst):
    n = len(lst)
    gap = n//2
    while gap >= 1:
        for i in range(gap,n):
            while i>=gap:
                if lst[i] < lst[i-gap]:
                    lst[i],lst[i-gap] = lst[i-gap],lst[i]
                i -= gap
        gap //= 2
xier_sort(lst)
print(lst)