谢尔排序Shell Sort

• 谢尔排序以插入排序作为基础
• 子列表的间隔一般从n/2开始
• 大致介于O(n)和O(n^2)之间，如果将间隔保持在 (1,3,5,7,15,31等等)，谢尔排序的时间复杂度约为O( )

def shellSort(alist):
    sublistcount = len(alist)//2  #间隔设定
    while sublistcount > 0:
        #子列表排序
        for startposition in range(sublistcount):
            gapInsertionSort(alist,startposition,sublistcount)
        print('After increments of size',sublistcount,'The list is',alist)
        sublistcount = sublistcount // 2 #间隔缩小
def gapInsertionSort(alist,start,gap):
    for i in range(start+gap, len(alist), gap):
        currentvalue = alist[i]
        position = i
        while position >= gap and alist[position-gap] > currentvalue:
            alist[position] = alist[position - gap]         
            position = position - gap
        alist[position] = currentvalue