今天周末陪老婆（我就不说程序猿苦逼了……），时间比较紧，因此这个时候才有空静下心写点东西。

   今天把希尔排序写了一遍，希尔排序相对于插入排序引入了增量的概念，就是一开始通过引入增量来把原来的表划分为几个子表。比如说之前9个元素，我取4为增量的话，那么0号跟4号为一组，1号跟5号，2号跟6号，3号跟7号，4号跟8号，5号单独一组，首先对每组进行插入排序。

   这样一轮大循环下来，每个字表序列都是好的。此时我把增量减小为2，那么这样的话，0、2、4、6、8为一组，1、3、5、7为一组。由于前一轮的优化，这次组内序列相对一开始较好，进行插入排序的操作复杂度会降低。

   最后取增量为1，这个时候就是对整个表进行插入排序了。可以这么说，插入排序就是增量为1的希尔排序。当然如何取好增量是提升效率的关键，这也导致了它的不稳定性，一般来说只有当n很大时，效率的提升才有所体现。对于增量incr的取值，一般初试取incr=n/3+1，然后依次取incr=incr/3+1，直到incr=1执行过一遍。

   代码如下：

def insert2(key,x,i,incr):    counter=0    while(i>=0 and key
     
      1):        for start in range(incr):            counter+=InsertionSort2(x,n,incr,start)        incr=int(incr/3)+1    counter+=InsertionSort2(x,n,1,1)    return counterx=[1,3,9,7,12,23,4,16,20]counter=ShellSort(x,len(x))for a in x:    print(a)print('times:'+str(counter))
     

   这里第22行可能有点费解，主要是由于python没有do……while循环，导致当incr为1时必须再手动执行一次。仔细看程序会发现它跟插入排序前两个函数其实很像，不过多了一个增量参数incr和表示子表下标的参数start。具体程序用纸笔走一遍流程应该能加深理解的。

   这个times的结果是24，比插入排序多了点，但还是要优于冒泡排序，主要是因为数据太少。为了更好的验证下，下面写个随机生成程序具体来验证一下：

import randomdef bubble(x):    counter=0    n=len(x)    for i in range(n):        for j in range(i,n-1):            counter+=1            if x[j]>x[j+1]:                t=x[j]                x[j]=x[j+1]                x[j+1]=t    return counterdef insert2(key,x,i,incr):    counter=0    while(i>=0 and key
     
      1):        for start in range(incr):            counter+=InsertionSort2(x,n,incr,start)        incr=int(incr/3)+1    counter+=InsertionSort2(x,n,1,1)    return counterdef insert(x,key,i):    counter=0    while (i>=0 and key
     

   这里结果袭来，bubble_sort始终为499500，insert_sort大概在60000-70000的水平，shell_sort大概在6494的水平，这个结果还是很明显的。今天不早了，先洗洗碎了，明天再好好把快排琢磨下做个比较。