希尔排序

参考https://www.jianshu.com/p/d730ae586cf3

希尔排序是怎么来的？

希尔排序是基于直接插入排序的以下两点性质而提出的改进方法：
1.插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
2.插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

（插入排序https://www.runoob.com/w3cnote/insertion-sort.html ）

希尔排序原理

希尔排序是将待排序的数组元素 按下标的一定增量分组 ，分成多个子序列，然后对各个子序列进行直接插入排序算法排序；然后依次缩减增量再进行排序，直到增量为1时，进行最后一次直接插入排序，排序结束。

增量的取值：初始以数组长度的一半为增量，之后每次为上一次的一般，直到增量为1

原理图解

代码实例

def shellsort(a):
    gap=len(a)//2
    while gap>0:
        for i in range(gap,len(a)):
            curr=a[i]
            preidx=i-gap
            while preidx>=0 and curr<a[preidx]:
                a[preidx+gap]=a[preidx]
                preidx-=gap
            a[preidx+gap]=curr
        gap=gap//2
    return a

print(shellsort([12,3,4,33,22,4,5]))