希尔排序（Shell Sort）

1. 算法描述
希尔排序是一种基于插入排序的改进算法，由Donald Shell于1959年提出。其核心思想是通过分组插入排序使数据逐渐趋于有序，最终进行一次完整的插入排序。希尔排序通过设定一个递减的增量序列（gap），对每组间隔gap的元素进行插入排序，随着gap逐渐减小，数据越来越接近有序，从而减少最后插入排序的比较和移动次数。

2. 增量序列的选择
增量序列的选择影响算法效率，常见选择包括：

• Shell原始序列：gap = n/2, n/4, ..., 1（递减至1）。
• Hibbard序列：gap = 2^k - 1（如1, 3, 7, 15...），最坏时间复杂度可优化至O(n^(3/2))。
  本例以Shell原始序列为例讲解。

3. 逐步排序过程
假设待排序数组为 [5, 2, 9, 1, 5, 6]，长度 n=6。

步骤1：初始增量gap = n/2 = 3
将数组分为3组（每组元素间隔3个位置）：

• 组1: [5, 1]
• 组2: [2, 5]
• 组3: [9, 6]
  对每组进行插入排序：
• 组1: [1, 5]
• 组2: [2, 5]
• 组3: [6, 9]
  排序后数组变为 [1, 2, 6, 5, 5, 9]。

步骤2：gap = 3/2 = 1（向下取整）
此时增量减至1，相当于对整个数组进行插入排序：

• 从第2个元素开始遍历（i=1到n-1），将每个元素插入到前部分的正确位置。
• 过程：
  • i=1: [1, 2, 6, 5, 5, 9]（2无需移动）
  • i=2: [1, 2, 6, 5, 5, 9]（6无需移动）
  • i=3: 5插入到6前 → [1, 2, 5, 6, 5, 9]
  • i=4: 5插入到5前（相等不移动） → [1, 2, 5, 5, 6, 9]
  • i=5: 9无需移动
    最终得到有序数组 [1, 2, 5, 5, 6, 9]。

4. 算法伪代码

ShellSort(arr):
    n = length(arr)
    gap = n / 2
    while gap > 0:
        for i from gap to n-1:
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap = gap / 2  # 减少增量

5. 关键点分析

• 分组排序的意义：大间隔的排序使元素快速移动到粗略位置，减少后续小间隔排序的移动距离。
• 稳定性：希尔排序是不稳定的（相同元素可能因分组交换而改变相对顺序）。
• 时间复杂度：
  • 最坏情况：O(n²)（如使用Shell原始序列）。
  • 优化序列可达到O(n^(1.5))或更低。

6. 与插入排序的对比
插入排序对部分有序数组效率高（接近O(n)）。希尔排序通过前期分组使数据逐步部分有序，充分利用了这一优势。