希尔排序又被称为缩小增量排序，是对直接插入排序的优化改进，它通过将待排序的数组按照一定增量分成多个子序列，对每个子序列进行插入排序，随着增量逐渐减小，整个数组会逐步接近有序状态，最后当增量减为1时，对整个数组进行一次直接插入排序即可完成整体排序。
基础希尔排序的 Java 数组实现
基础希尔排序通常使用初始增量为数组长度的一半，之后每次将增量减半，直到增量变为1。以下是基于数组的基础实现代码：
public class ShellSortDemo {
// 基础希尔排序方法，参数为待排序的整型数组
public static void basicShellSort(int[] arr) {
// 初始增量设为数组长度的一半
int gap = arr.length / 2;
// 增量大于0时持续循环
while (gap > 0) {
// 对每个子序列进行插入排序
for (int i = gap; i < arr.length; 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;
}
// 增量减半
gap /= 2;
}
}
public static void main(String[] args) {
int[] testArr = {9, 1, 5, 8, 3, 7, 4, 6, 2};
System.out.println("排序前数组：");
for (int num : testArr) {
System.out.print(num + " ");
}
basicShellSort(testArr);
System.out.println("n排序后数组：");
for (int num : testArr) {
System.out.print(num + " ");
}
}
}
增量序列对希尔排序的影响
增量序列的选择直接决定了希尔排序的时间复杂度，不同的增量序列会带来完全不同的排序性能，下面分析几种常见的增量序列及其优化方向。
1. 基础减半增量序列
也就是上面实现中使用的gap = arr.length / 2，之后 gap /= 2的序列，这种序列实现简单，但存在明显缺陷：当增量序列中的值有公因子时，会导致某些元素多次被分到同一个子序列，无法充分发挥分组排序的作用，最坏时间复杂度为O(n²)。
2. Hibbard 增量序列
Hibbard 增量序列的公式为gap = 2^k - 1，其中k从1开始递增，直到2^k - 1 < 数组长度。这种序列的相邻增量互质，避免了公因子问题，最坏时间复杂度可以降到O(n^(3/2))，实现方式如下：
public static void hibbardShellSort(int[] arr) {
// 计算最大的Hibbard增量
int k = 1;
while ((int)Math.pow(2, k) - 1 < arr.length) {
k++;
}
k--;
int gap = (int)Math.pow(2, k) - 1;
// 按Hibbard序列递减增量
while (gap > 0) {
for (int i = gap; i < arr.length; 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;
}
// 计算下一个Hibbard增量
k--;
if (k >= 1) {
gap = (int)Math.pow(2, k) - 1;
} else {
gap = 0;
}
}
}
3. Sedgewick 增量序列
Sedgewick 增量序列是通过组合两种公式计算得到的，性能比 Hibbard 序列更优，最坏时间复杂度可以达到O(n^(4/3))，是目前实践中表现较好的增量序列之一，不过实现逻辑相对复杂，需要根据序列公式生成对应的增量数组再使用。
增量序列优化对比
以下是几种常见增量序列的特性对比：
| 增量序列类型 | 最坏时间复杂度 | 实现复杂度 | 适用场景 |
|---|---|---|---|
| 基础减半序列 | O(n²) | 低 | 数据量小、对性能要求不高的场景 |
| Hibbard 序列 | O(n^(3/2)) | 中等 | 中等数据量、需要平衡实现成本和性能的场景 |
| Sedgewick 序列 | O(n^(4/3)) | 高 | 大数据量、对排序性能要求较高的场景 |
实现注意事项
- 希尔排序是不稳定排序，相同值的元素在排序后相对位置可能发生变化，如果需要稳定排序则不适合使用。
- 增量序列的最后一个值必须为1，否则无法保证数组最终完全有序。
- 对于基本有序的数组，希尔排序的性能会接近直接插入排序，效率较高。
实际开发中如果没有特殊性能要求，使用基础减半增量序列即可满足需求，若需要处理大量数据，建议选择 Hibbard 或 Sedgewick 增量序列来提升排序效率。