希尔排序(缩小增量排序)

原理

将一个无序集合分割成多个子集合进行直接插入排序并交换存储位置，
然后将排序结果继续分为多个子集合排序交换存储位置，
每次子集合的数量递减，直到到子集合个数为1时进行最后一次直接插入排序。
希尔排序需要关注的一点就是每次我们隔多少个元素拆分集合（术语是增量因子），
所以通过增量因子（每组多少个元素）确定子集合的个数很重要，但最终一次排序的增量因子必须是1。

例：

原始集合：{5,2,4,6,8,1,9,7,10,3}
分割集合：{5,1} {2,9} {4,7} {6,10} {3,8}  每隔5个元素分一个子集合
第一次排序：{1,5} {2,9} {4,7} {6,10} {8,3} => {1,2,4,6,3,5,9,7,10,8}
分割集合：{1,6,9,8} {2,3,7} {4,5,10} 每隔3个元素分一个子集合
第二次排序：{1,6,8,9} {2,3,7} {4,5,10} => {1,2,4,6,3,5,8,7,10,9}
分割集合：{1},{2},{4},{6},{3},{5},{8},{7},{10},{9} 每隔1个元素分一个子集合
最后直插排序：{1,2,3,4,5,6,7,8,9,10}

原理图

暂无

实现

inputArr = [10, 34, 29, 4, 0, 34, 5, 4, 36, 1, 8]
print("未排序集合:{0}".format(inputArr))
length = len(inputArr)
gap = length//2
# 直到增量因子等于0时排序完成
while (gap > 0):
    # 按增量因子分组排序
    for index in range(0, gap):
        # 使用直接插入排序对分组内的数据排序
        currIndex=index
        while(currIndex<length):
            gapIndex=currIndex+gap
            while(gapIndex < length):
                if(inputArr[currIndex] > inputArr[gapIndex]):
                    inputArr[currIndex], inputArr[gapIndex] = inputArr[gapIndex], inputArr[currIndex]
                    break
                gapIndex += gap
            currIndex+=gap
    gap //= 2
print("已排序集合:{0}".format(inputArr))