1、算法步骤

a. 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

b. 按增量序列个数 k，对序列进行 k 趟排序；

c. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

2、动图演示

3、代码

# 定义一个函数shellSort，参数为一个列表arr
def shellSort(arr):
    # 导入math模块
    import math
    # 初始化间隔为1
    gap = 1
    # 计算增量序列的最大值
    while gap < len(arr) / 3:
        gap = gap * 3 + 1
    # 希尔排序过程
    while gap > 0:
        # 对间隔为gap的元素进行插入排序
        for i in range(gap, len(arr)):
            # 记录当前元素的值
            temp = arr[i]
            # j为当前元素的前一个元素的索引
            j = i - gap
            # 插入排序过程，将比temp大的元素向后移动gap个位置
            while j >= 0 and arr[j] > temp:
                arr[j + gap] = arr[j]
                j -= gap
            # 将temp插入到合适的位置
            arr[j + gap] = temp
        # 缩小增量
        gap = math.floor(gap / 3)
    # 返回排序后的列表arr
    return arr

打赏 支付宝打赏 微信打赏