希尔排序

参考: 希尔排序(图文并茂)

# shellsort


def shell_sort(li):
    n = len(li)
    # 设置 步长
    gap = n // 2
    # 步长从大到小，最后必须按照1步长排序
    while gap >= 1:

        # 从步长位置遍历剩下数据，分组，让每组的数据排序
        for i in range(gap, n):

            # 拿当前位置与减步长的位置的数据比较
            while (i - gap) >= 0:
                if li[i] < li[i - gap]:
                    li[i], li[i - gap] = li[i - gap], li[i]
                    i -= gap
                else:
                    break
        gap //= 2


if __name__ == '__main__':
    l = [6, 5, 6, 3, 2, 7]
    shell_sort(l)
    print(l)

    # 稳定性：不稳定
    # 时间复杂度：跟步长相关