原理:

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本,该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量（gap）”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率比直接插入排序有较大提高。

• 插入排序就是增量为1的希尔排序
• gap：初始值元素个数整除2

5 3 6 4 1 8

gap = 长度//2 = 3 分别以不同颜色表示分组

第一遍:

• 5>4 互换4 3 6 5 1 8
• 3>1 互换4 1 6 5 3 8
• 6<8 不变

缩减gap 3//2 = 1

此时只有一组,直接进行插入排序即可.(事实上当gap等于2时,数据被分成2组,而不会2个一组两个一组),希尔排序实则是对插入排序的优化.

 代码实现:

        核心代码:

        while i >= gap:
            if alist[i] < alist[i-gap]:
                alist[i],alist[i-gap] = alist[i-gap],alist[i]
                i -= gap
            else:
                break 

完整代码实现:

def sort(alist):
    gap = len(alist)//2

    while gap >= 1:
        #将下属所有的1换成gap
        for i in range(gap,len(alist)):
            while i >= gap:
                if alist[i] < alist[i-gap]:
                    alist[i],alist[i-gap] = alist[i-gap],alist[i]
                    i -= gap
                else:
                    break
        gap //= 2 #缩减增量
    return alist