希尔排序

希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

import random
import time
import sys


def shell_sort(li):
    gap = len(li) // 2
    while gap > 0:
        for i in range(gap, len(li)):
            tmp = li[i]
            j = i - gap
            while j >= 0 and tmp < li[j]:
                li[j+gap] = li[j]
                j -= gap
            li[j+gap] = tmp
        gap //= 2


sys.setrecursionlimit(10000)
data = list(range(10000))
random.shuffle(data)
t1 = time.time()
print('排序前：{}'.format(data))
shell_sort(data)
print('排序后：{}'.format(data))
t2 = time.time()
print('时间：{}'.format(t2-t1))