希尔排序

希尔排序时插入排序的一种，是直接插入排序算法的一种更高效的改进版本。该方法因 D.L.Shell 于 1959 年提出而得名。
希尔排序是基于插入排序而改进的：

1. 插入排序对几乎已经排好序的数据操作时，效率高，即可达到线性排序的效率。
2. 插入排序一般来说是低效的，因为插入排序只能将数据移动一位。

基本思想

先取一个小于 n 的整数 d1 作为第一个增量，把文件的全部记录分组。所有距离为 d1 的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序
直至所取的增量 dt = 1(<…<d2<d1)
即所有记录放在同一组中进行直接插入排序为止。

一般的初次取序列的一半为增量，以后每次减半，直到增量为1。

稳定性

由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以 shell 排序是不稳定的。

希尔分析

希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。

def Shell_sort(L):
# 引用至：https://www.cnblogs.com/xubing-613/p/7286203.html
    step = len(L)/2
    while step > 0:
        for i in range(step,len(L)):            #在索引为step到len（L）上，比较L[i]和L[i-step]的大小
            while(i >= step and L[i] < L[i-step]):      #这里可以调整step从小到大或者从大到小排列
                L[i],L[i-step] = L[i-step],L[i]
                i -= step
                # print L
        step /= 2
    print L

运行结果.png

我自己画了个图，给自己看

过程.png