希尔排序

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
一般的初次取序列的一半为增量，以后每次减半，直到增量为1。

def shell_sort(alist):
    n = len(alist)
    gap = n // 2
    while gap >= 1:
        for j in range(1,n):
            for i in range(j,0,-1):
                if alist[i] < alist[i-gap]:
                    alist[i],alist[i-gap] = alist[i-gap],alist[i]
                else:
                    break
        gap = gap // 2
    return alist
 
if __name__ == '__main__':
    li = [1, 3, 4, 2, 9, 5, 8]
    print(li)
    shell_sort(li)
    print(li)

希尔排序是基于插入排序上的，因为插入排序每次一个一个数据的交换效率太低了，希尔排序是不稳定的

时间复杂度：最优O(n^^1.3)-->数据分析出来的，最坏O(n**2）