希尔排序 Python

碎碎念念

希尔排序是插入排序的一种，是直接插入排序的改进版。

我们首先来看直接插入排序，其基本思路是，一般先孤立这堆数字的第一个数，那么它自己一个就是有序了，再拿后面的数和它比较，找到大小位置合适的插进去，完了之后这一小堆还是有序的，再拿后面的来和前面的比较，找到合适的位置插进去，直到全部插完。

直接插入排序的优势

从直接插入排序的思想可以知道，如果这堆数原本就比较有序了，那么直接插入排序是非常高效的，因为交换次数会少很多。

直接插入排序的劣势

但有一种情况是，假设是从小到大排序，前面已经排好了一万个有序数，到这10001个数的时候，恰好它是最小的那一个，那么就要和前面的数全部交换一次，，这就出现了交换距离过长的问题，这是我们不希望看到的。

希尔排序

基于直接插入排序的这两个特点，我们引入了它的升级版——希尔排序。

希尔排序又被称作缩小增量排序。

为了解决直接插入排序交换距离过长问题，我们设想如果能让这一堆待排序的数中比较小的数在一边，比较大的数在另一边，那么发生交换的时候就不用跨过千山万水了。

也就是说，我们要先对这一堆数进行预排序，具体操作是，先选定一个数interval（一般是数字的总数的一半）作为第一增量，然后把间隔为interval的数作为一个小组，对这个小组进行直接插入排序，然后缩小interval（一般是让interval减半）作为第二增量，继续分小组进行直接插入排序，以此类推，操作下去，到interval等于1的时候，小组间间隔为1，也就是对全部元素进行直接插入排序，但整个时候，这一堆数已经相对有序了，直接插入排序这个时候就十分高效了

代码

def insert(number,n):#从小到大排序
    interval=int(n/2)
    while interval>0:
        for i in range(1,n,interval):#以interval为间隔划分小组
            for j in range(i,0,-interval):#小组内进行直接插入排序
                if number[j-interval]>number[j]:
                    number[j-interval],number[j]=number[j],number[j-interval]
        interval=int(interval/2)
number=[1,3,6,8,2,5,4,9,0,7]
insert(number,10)
print(number)