希尔排序算法详解：原理、实现与优化
一、算法概述
希尔排序 (Shell Sort) 是 Donald Shell 于 1959 年提出的一种改进的插入排序算法，又称缩小增量排序。它通过将原始数组分解为若干个子序列进行插入排序，随着增量逐渐减小，最终对整个数组进行一次插入排序。
基本特性
- 时间复杂度：取决于增量序列，通常为 O(n^(1.3-2))
- 空间复杂度：O(1)（原地排序）
- 稳定性：不稳定排序算法
- 适用场景：中等规模数据，特别是部分有序的数据
二、算法原理详解
核心思想
- 分组插入排序：按照增量 gap 将数组分为若干子序列
- 逐步缩小增量：每次缩小 gap 值，直到 gap=1
- 最终插入排序：当 gap=1 时，就是标准的插入排序
增量序列选择
常用的增量序列：
- Shell 原始序列：gap = n/2, n/4, …, 1
- Hibbard 序列：1, 3, 7, …, 2^k-1
- Sedgewick 序列：1, 5, 19, 41, 109,…
三、算法流程图示
示例数组：[8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
初始状态
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 8 │ 9 │ 1 │ 7 │ 2 │ 3 │ 5 │ 4 │ 6 │ 0 │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
第一轮：gap=5
将数组分为 5 组：(8,3), (9,5), (1,4), (7,6), (2,0)
分组示意图：
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 8 │ │ │ │ │ 3 │ │ │ │ │ → (8,3)
│ │ 9 │ │ │ │ 5 │ │ │ │ │ → (9,5)
│ │ │ 1 │ │ │ │ 4 │ │ │ │ → (1,4)
│ │ │ │ 7 │ │ │ │ 6 │ │ │ → (7,6)
│ │ │ │ │ 2 │ │ │ │ 0 │ │ → (2,0)
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
排序后结果：
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 3 │ 5 │ 1 │ 6 │ 0 │ 8 │ 9 │ 4 │ 7 │ 2 │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
第二轮：gap=2
将数组分为 2 组：(3,1,0,9,7), (5,6,8,4,2)
分组示意图：
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 3 │ │ 1 │ │ 0 │ │ 9 │ │ 7 │ │ → (3,1,0,9,7)
│ │ 5 │ │ 6 │ │ 8 │ │ 4 │ │ 2 │ → (5,6,8,4,2)
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
排序后结果：
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 2 │ 1 │ 4 │ 3 │ 5 │ 7 │ 6 │ 9 │ 8 │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
第三轮：gap=1（标准插入排序）
最终排序结果：
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
