引言
希尔排序（Shell Sort）是插入排序的一种高效改进版本，由计算机科学家 Donald Shell 于 1959 年提出。它通过引入”增量序列”的概念，让相距一定间隔的元素先进行局部有序化，逐步缩小间隔直至为 1，最终完成全局排序。这种策略使得希尔排序在处理大规模数据时，时间复杂度远优于普通的 O(n²) 插入排序，最优可达 O(n log n)。本文将用 Java 完整实现希尔排序，并深入分析不同增量序列对性能的影响。
希尔排序的核心思想
普通插入排序的问题在于：当最小的元素位于数组末尾时，需要经过 n-1 次移动才能到达正确位置。希尔排序通过允许交换相距较远的元素，让小的元素可以”大步前进”，从而在前期快速改善数组的有序程度。
希尔排序的执行过程可以概括为：
– 选择一个增量序列 gap₁, gap₂, …, gapₖ，其中 gapₖ = 1
– 对于每个增量 gap，将数组分成 gap 个子序列，每个子序列由间隔为 gap 的元素组成
– 对每个子序列执行插入排序
– 当增量缩小到 1 时，数组已经”基本有序”，此时普通插入排序只需少量移动即可完成
经典增量序列
1. Shell 原始序列（gap = n/2, n/4, …）
最直观的增量序列，每次将增量减半。
2. Hibbard 序列（gap = 2^k – 1）
增量为 1, 3, 7, 15, 31, …，时间复杂度约为 O(n^1.5)。
3. Sedgewick 序列
结合了 9×4^k – 9×2^k + 1 和 4^k – 3×2^k + 1 的混合序列，时间复杂度约为 O(n^1.3)。
Java 实现
基础希尔排序（Shell 原始序列）
/**
* 希尔排序基础实现
* 使用 Shell 原始增量序列：n/2, n/4, n/8, ..., 1
* 时间复杂度：最坏 O(n²)，平均约为 O(n^1.3) ~ O(n^2)
* 空间复杂度：O(1)
* 稳定性：不稳定排序
*/
public class ShellSort {
/**
* 希尔排序主方法
* @param arr 待排序的整型数组
*/
public static void shellSort(int[] arr) {
int n = arr.length;
// 初始增量为数组长度的一半，逐步折半
for (int gap = n / 2; gap > 0; gap /= 2) {
// 对每个子序列执行插入排序
// 从第 gap 个元素开始，逐个向所属子序列中插入
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j = i;
// 在子序列中寻找插入位置
// arr[j - gap] > temp 确保找到比 temp 小的元素为止
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap]; // 元素后移
j -= gap; // 在同一子序列中向前比较
}
arr[j] = temp; // 将 temp 放入正确位置
}
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90, 5, 77, 30};
System.out.println("排序前: " + java.util.Arrays.toString(arr));
shellSort(arr);
System.out.println("排序后: " + java.util.Arrays.toString(arr));
}
}
Hibbard 增量序列实现
/**
* 使用 Hibbard 增量序列的希尔排序
* Hibbard 序列：1, 3, 7, 15, 31, ... (2^k - 1)
* 理论时间复杂度约为 O(n^1.5)
*/
public static void shellSortHibbard(int[] arr) {
int n = arr.length;
// 预计算不超过 n 的最大 Hibbard 增量
// 找到最大的 k，使得 2^k - 1 <= n
int k = 1;
while ((1 << (k + 1)) - 1 <= n) {
k++;
}
// 从大到小遍历 Hibbard 增量
for (; k >= 1; k--) {
int gap = (1 << k) - 1; // 2^k - 1
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
Sedgewick 增量序列实现
/**
* 使用 Sedgewick 增量序列的希尔排序
* 该序列混合了 9*4^k - 9*2^k + 1 和 4^k - 3*2^k + 1
* 是目前已知表现最好的增量序列之一，时间复杂度约 O(n^1.3)
*/
public static void shellSortSedgewick(int[] arr) {
int n = arr.length;
// 预计算 Sedgewick 增量序列
java.util.ArrayList<Integer> gaps = new java.util.ArrayList<>();
int k = 0;
int gap;
while (true) {
if (k % 2 == 0) {
gap = 9 * (1 << (2 * k)) - 9 * (1 << k) + 1;
} else {
gap = (1 << (2 * k + 2)) - 3 * (1 << (k + 1)) + 1;
}
if (gap > n) break;
gaps.add(gap);
k++;
}
// 从大到小应用增量
for (int idx = gaps.size() - 1; idx >= 0; idx--) {
int g = gaps.get(idx);
for (int i = g; i < n; i++) {
int temp = arr[i];
int j = i;
while (j >= g && arr[j - g] > temp) {
arr[j] = arr[j - g];
j -= g;
}
arr[j] = temp;
}
}
}
排序过程可视化
以数组 [64, 34, 25, 12, 22, 11, 90, 5] 为例，使用 Shell 原始序列（gap = 4, 2, 1）：
gap = 4 时：
– 子序列 1（索引 0, 4）：[64, 22] → 排序后 [22, 64]
– 子序列 2（索引 1, 5）：[34, 11] → 排序后 [11, 34]
– 子序列 3（索引 2, 6）：[25, 90] → 已有序
– 子序列 4（索引 3, 7）：[12, 5] → 排序后 [5, 12]
– 数组变为：[22, 11, 25, 5, 64, 34, 90, 12]
gap = 2 时：
– 子序列 1（索引 0, 2, 4, 6）：[22, 25, 64, 90] → 已有序
– 子序列 2（索引 1, 3, 5, 7）：[11, 5, 34, 12] → 排序后 [5, 11, 12, 34]
– 数组变为：[22, 5, 25, 11, 64, 12, 90, 34]
gap = 1 时（普通插入排序）：
– 数组已基本有序，只需少量移动即可得到最终结果
不同增量序列性能对比
| 增量序列 | 最坏时间复杂度 | 平均时间复杂度 | 额外空间 |
|---|---|---|---|
| Shell (n/2^k) | O(n²) | O(n log n) ~ O(n²) | O(1) |
| Hibbard (2^k-1) | O(n^1.5) | O(n^1.5) | O(1) |
| Sedgewick | O(n^1.3) | O(n^1.3) | O(1) |
| Knuth (3k+1) | O(n^1.5) | O(n^1.5) | O(1) |
完整测试与性能评测
import java.util.Arrays;
import java.util.Random;
public class ShellSortBenchmark {
public static void main(String[] args) {
int[] sizes = {1000, 10000, 100000};
Random rand = new Random(42);
for (int size : sizes) {
int[] arr1 = new int[size];
int[] arr2 = new int[size];
int[] arr3 = new int[size];
for (int i = 0; i < size; i++) {
int val = rand.nextInt(size * 10);
arr1[i] = val;
arr2[i] = val;
arr3[i] = val;
}
System.out.println("\n数组大小: " + size);
long t1 = System.currentTimeMillis();
ShellSort.shellSort(arr1);
System.out.println("Shell 原始序列: " + (System.currentTimeMillis() - t1) + "ms");
long t2 = System.currentTimeMillis();
ShellSort.shellSortHibbard(arr2);
System.out.println("Hibbard 序列: " + (System.currentTimeMillis() - t2) + "ms");
long t3 = System.currentTimeMillis();
ShellSort.shellSortSedgewick(arr3);
System.out.println("Sedgewick 序列: " + (System.currentTimeMillis() - t3) + "ms");
}
}
}
总结
希尔排序是对插入排序的精妙改进，通过增量序列让元素能够”大步前进”，有效解决了普通插入排序中逆序对过多导致的效率问题。虽然希尔排序不是稳定排序，且最坏时间复杂度取决于增量序列的选择，但其实现简单、原地排序、无需递归栈空间的特点，使其在嵌入式系统和内存受限环境中仍有广泛应用。Sedgewick 增量序列是实际应用中表现最优的选择之一，值得在工程实践中优先考虑。
