排序过程可视化

初始数组: [9, 8, 7, 6, 5, 4, 3, 2, 1]

1. gap=4: 分组为 [9,5,1], [8,4], [7,3], [6,2] → 排序后 [1,4,3,2,5,8,7,6,9]
2. gap=2: 分组为 [1,3,5,7,9], [4,2,8,6] → 排序后 [1,2,3,4,5,6,7,8,9]
3. gap=1: 对整个数组插入排序 → 最终排序完成

def shell_sort(arr):
    """
    希尔排序算法的Python实现
    
    参数:
        arr (list): 待排序的列表
        
    返回:
        list: 排序后的列表
    """
    n = len(arr)
    # 初始间隔取列表长度的一半
    gap = n // 2
    
    # 当间隔大于0时持续循环
    while gap > 0:
        # 对每个子序列进行插入排序
        for i in range(gap, n):
            # 保存当前元素值
            temp = arr[i]
            j = i
            # 对子序列进行插入排序
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            # 将保存的值插入到正确位置
            arr[j] = temp
        # 缩小间隔
        gap //= 2
    
    return arr

# 测试希尔排序
if __name__ == "__main__":
    test_array = [33, 12, 56, 9, 23, 45, 87, 3, 67, 21]
    print("排序前:", test_array)
    sorted_array = shell_sort(test_array.copy())
    print("排序后:", sorted_array)

时间复杂度对比