以下是希尔排序的详细解析，包含基础实现、常见变体的完整代码示例，以及各变体的对比表格：
一、希尔排序基础实现
原理
希尔排序是插入排序的改进版本，通过分步缩小增量间隔，将数组分成多个子序列进行插入排序，逐步减少元素移动次数。
代码示例
public class ShellSort {void sort(int[] arr) {int n = arr.length;// 初始增量（希尔原始增量：n/2，每次除以2）for (int gap = n / 2; gap > 0; gap /= 2) {// 对每个子序列进行插入排序for (int i = gap; i < n; i++) {int temp = arr[i];int j;// 插入排序，步长为gapfor (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap];}arr[j] = temp;}}}
}
复杂度分析
- 时间复杂度：
- 平均：
O(n^(3/2))（希尔原始增量）。 - 最坏：
O(n²)（依赖增量序列）。 - 最好：
O(n log n)。
- 平均：
- 空间复杂度：
O(1)。 - 稳定性：不稳定（相同值的元素可能因交换顺序改变相对位置）。
二、常见变体及代码示例
1. Hibbard增量序列
改进点：增量序列选择 2^k - 1（如1、3、7、15…），减少子序列间的相关性。
适用场景：平均性能优于原始希尔增量。
public class HibbardShellSort {void sort(int[] arr) {int n = arr.length;// 生成Hibbard增量序列int gap = 1;while (gap < n / 2) {gap = 2 * gap + 1;}while (gap >= 1) {for (int i = gap; i < n; i++) {int temp = arr[i];int j;for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap];}arr[j] = temp;}gap = (gap - 1) / 2; // 逆序应用增量}}
}
2. Sedgewick增量序列
改进点：增量序列按特定公式生成（如1, 5, 19, 41, 109…），优化时间复杂度。
适用场景：理论时间复杂度更低（接近 O(n^(4/3))）。
public class SedgewickShellSort {void sort(int[] arr) {int n = arr.length;// 生成Sedgewick增量序列List<Integer> gaps = new ArrayList<>();for (int h = 1; h < n; ) {gaps.add(h);if (h <= n / 3) h = 3 * h + 1;else h = 3 * (h / 2) + 1;}// 逆序应用增量for (int i = gaps.size() - 1; i >= 0; i--) {int gap = gaps.get(i);for (int j = gap; j < n; j++) {int temp = arr[j];int k;for (k = j; k >= gap && arr[k - gap] > temp; k -= gap) {arr[k] = arr[k - gap];}arr[k] = temp;}}}
}
3. 斐波那契增量序列
改进点：增量序列基于斐波那契数列（如1、1、2、3、5…），减少子序列相关性。
适用场景：理论上的优化尝试。
public class FibonacciShellSort {void sort(int[] arr) {int n = arr.length;// 生成斐波那契增量序列List<Integer> gaps = new ArrayList<>();int a = 0, b = 1;while (b < n) {gaps.add(b);int temp = a + b;a = b;b = temp;}// 逆序应用增量for (int i = gaps.size() - 1; i >= 0; i--) {int gap = gaps.get(i);for (int j = gap; j < n; j++) {int temp = arr[j];int k;for (k = j; k >= gap && arr[k - gap] > temp; k -= gap) {arr[k] = arr[k - gap];}arr[k] = temp;}}}
}
三、变体对比表格
| 变体名称 | 增量序列 | 时间复杂度 | 空间复杂度 | 稳定性 | 主要特点 | 适用场景 |
|---|---|---|---|---|---|---|
| 基础希尔排序（原始增量） | n/2, n/4, ..., 1 | O(n^(3/2))（平均）O(n²)（最坏） | O(1) | 不稳定 | 简单易实现，但性能依赖增量选择 | 通用场景，增量选择简单 |
| Hibbard增量序列 | 2^k -1（如1,3,7,15…） | O(n^(3/2))（平均） | O(1) | 不稳定 | 减少子序列相关性，性能更优 | 需要平衡性能与实现复杂度的场景 |
| Sedgewick增量序列 | 1,5,19,41,… | O(n^(4/3))（理论最优） | O(1) | 不稳定 | 理论时间复杂度最低，适合大数据 | 需要极致性能的场景 |
| 斐波那契增量序列 | 斐波那契数列（如1,2,3…） | O(n^(3/2))（平均） | O(1) | 不稳定 | 理论上的优化尝试，实际效果需验证 | 研究或特定实验场景 |
四、关键选择原则
- 基础场景：优先使用基础希尔排序（原始增量），因其简单且性能足够。
- 性能优化：
- Hibbard增量：适合需要比原始增量更好的平均性能，且实现复杂度较低。
- Sedgewick增量：适用于大数据场景，理论时间复杂度最低。
- 增量序列选择：
- 理论最优：Sedgewick增量。
- 实现简单：Hibbard增量。
- 稳定性需求：所有变体均不稳定，若需稳定排序需选择其他算法（如归并排序）。
- 实验场景：斐波那契增量可用于探索不同增量序列的效果，但实际应用较少。
通过选择合适的增量序列，可在特定场景下显著提升希尔排序的效率。例如，Sedgewick增量在理论上的时间复杂度最低，适合大数据排序；而Hibbard增量则在实现复杂度与性能之间取得平衡。
