希尔排序算法（Shell Sort）

# /*
# 希尔排序算法（Shell Sort）
# --------------------------------------------------------
# 原理：
# 又称“缩小增量排序”。在插入排序基础上改进。
# 通过设置“步长 gap”，让相距 gap 的元素分组执行插入排序，
# 随着 gap 不断缩小，最终 gap = 1 时再次执行插入排序，
# 达到整体有序的效果。
#
# 这种先粗排、再细排的方式，可明显减少移动次数，提高效率。
# */

def shell_sort(arr):
    n = len(arr)
    gap = n // 2   # 初始步长设为序列长度的一半

    # gap 持续缩小直到为 1
    while gap > 0:
        # 从 gap 开始做插入排序
        for i in range(gap, n):
            temp = arr[i]
            j = i

            # 类似插入排序，但比较的是相隔 gap 的元素
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap

            arr[j] = temp

        # 缩小步长
        gap //= 2

    return arr


# 示例演示
data = [12, 34, 54, 2, 3]
print("排序前：", data)
sorted_data = shell_sort(data)
print("排序后：", sorted_data)

# --------------------------------------------------------
# 关键要点总结：
# 1) 希尔排序是插入排序的优化版本；
# 2) 步长 gap 决定分组方式，gap 逐步减小到 1；
# 3) 时间复杂度依赖步长序列，一般约为 O(n^1.3 ~ n^2)；
# 4) 不稳定排序（元素可能跨越较远的位置交换）；
# 5) 适合中等规模数据，比简单 O(n²) 排序更快。
# */
#
# 排序前： [12, 34, 54, 2, 3]
# 排序后： [2, 3, 12, 34, 54]