希尔排序

1.概念

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
希尔排序是把记录按一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

2.算法描述

1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2. 按增量序列个数k，对序列进行k 趟排序；
3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

希尔排序是插入排序改良的算法，希尔排序步长从大到小调整，第一次循环后面元素逐个和前面元素按间隔步长进行比较并交换，直至步长为1，步长选择是关键。

直接上图比较好懂：


如果还没懂，看一下动图演示：

3.python代码实现

def shell_sort(s):
    n=len(s)
    gap=n//2
    while gap>=1:
        #j是需要比较的次数
        for j in range(gap,n): #3,4,5
            #i是需要控制的索引
            i=j
            while (i-gap)>=0 and s[i]<s[i-gap]:
                    #交换
                    s[i],s[i-gap]=s[i-gap],s[i]
                    #修改i
                    i-=gap
        #控制间隙变化
        gap//=2
    return s
s=[2,8,9,1,3]
shell_sort(s)

4.算法分析

最佳情况：T(n) = O(nlog2 n) 最坏情况：T(n) = O(nlog2 n) 平均情况：T(n) =O(nlog2n)　不稳定