🧮 希尔排序 (Shell Sort)

难度 / Difficulty: 中等 (Medium)
分类 / Category: 插入排序改进 (Insertion Sort Variant)
时间复杂度 / Time Complexity: O(n^1.3) ~ O(n²)
空间复杂度 / Space Complexity: O(1)

📖 算法简介 / Introduction

希尔排序是插入排序的改进版本，由 Donald Shell 于 1959 年提出。核心思想是设置递减的间隔，先对间隔较大的子序列进行排序（让元素快速移动到正确位置），逐步减少间隔直到 1。

Shell sort is an improved version of insertion sort, proposed by Donald Shell in 1959. The key idea is to use a decreasing gap sequence — first sort sub-arrays with large gaps, then progressively reduce the gap until it becomes 1.

💡 算法原理 / Principle

1. 设置间隔：选择一个递减的间隔序列（如 n/2, n/4, …, 1）
2. 分组排序：对于每个间隔 g，将数组分为 g 个子序列，每个子序列间隔 g 个元素
3. 插入排序：对每个子序列使用插入排序
4. 缩小间隔：重复以上过程，直到间隔为 1

核心思想：大的间隔让元素可以远距离跳跃，减少移位次数

为什么比插入排序快？插入排序每次只移动相邻元素，希尔排序通过大间隔让元素一次性移动更远的距离，减少总体移位次数。

📝 代码实现 / Implementation

def shell_sort(arr):
    n = len(arr)
    
    # 设置初始间隔（n/2）
    gap = n // 2
    
    while gap > 0:
        # 对每个间隔为 gap 的子序列进行插入排序
        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

✨ 示例 / Example

输入数组：[12, 34, 54, 2, 3, 45, 8]

Step 1: gap = 7 // 2 = 3
分组：[12, 2, 8] 和 [34, 3] 和 [54, 45]
子序列排序后：[2, 8, 12] 和 [3, 34] 和 [45, 54]
数组变为：[2, 3, 45, 12, 34, 54, 8]

Step 2: gap = 3 // 2 = 1
使用插入排序对整个数组排序
最终：[2, 3, 8, 12, 34, 45, 54]

🎯 适用场景 / Scenarios

• 中等规模数据 — 数据量在几千到几万时效率较好
• 接近有序的数据 — 比普通插入排序更快
• 嵌入式系统 — 原地排序，空间复杂度 O(1)
• 初步学习排序 — 理解插入排序改进思路

Medium-sized datasets, Nearly sorted data, Space-constrained environments, Understanding insertion sort improvements.

⚠️ 优缺点 / Pros & Cons

🔄 间隔序列的选择 / Gap Sequence Options