4.排序算法（4）

1.希尔排序图示

2.代码实现

lst = [8,4,0,9,2,7,3,1,5]    #测试案例

print('origin',lst)
print('*'*30)

def shell_sort2(arr):
    iter_num = 0
    gap = len(arr)//2  # 初始步长设置为总长度的一半
    while gap >= 1:
        iter_num += 1
        for i in range(gap,len(arr)):
            while i >= gap and arr[i-gap] > arr[i]:  # 在每一组里面进行直接插入排序
                arr[i], arr[i-gap] = arr[i-gap],arr[i]
                i -= gap
        print(iter_num, arr)
        gap = gap // 2  # 更新步长
    return arr

sorted_lst = shell_sort2(lst)
print('*'*30)
print('sorted',sorted_lst)

# 运行结果
origin [8, 4, 0, 9, 2, 7, 3, 1, 5]
******************************
1 [2, 4, 0, 1, 5, 7, 3, 9, 8]
2 [0, 1, 2, 4, 3, 7, 5, 9, 8]
3 [0, 1, 2, 3, 4, 5, 7, 8, 9]
******************************
sorted [0, 1, 2, 3, 4, 5, 7, 8, 9]

附录：另一种思路，方法略有不同

def shell_sort(arr):
    iter_num = 0
    gap = len(arr)//2
    while gap >= 1:
        iter_num += 1
        for i in range(gap,len(arr)):
            while i>0:
                if arr[i] < arr[i-gap]:
                    arr[i],arr[i-gap] = arr[i-gap],arr[i]
                    i -= gap
                else:
                    break
        print(iter_num, lst)
        gap //= 2
    return arr

# 运行结果
origin [8, 4, 0, 9, 2, 7, 3, 1, 5]
******************************
1 [1, 4, 0, 5, 2, 7, 3, 9, 8]
2 [0, 4, 1, 5, 2, 7, 3, 9, 8]
3 [0, 1, 2, 3, 4, 5, 7, 8, 9]
******************************
sorted [0, 1, 2, 3, 4, 5, 7, 8, 9]