1. 简介
本文将介绍如何在 Java 中实现 Shell 排序（Shell Sort）算法。
2. Shell 排序概述
2.1 算法描述
Shell 排序是插入排序（Insertion Sort）的一种改进版本，属于高效排序算法之一。其核心思想是：
- 将原始数组划分为若干个子序列（子集）
- 对每个子序列进行插入排序
- 随着子序列间隔（gap）逐步缩小，最终完成一次完整的插入排序
与普通插入排序不同的是，Shell 排序并不是按相邻元素划分子序列，而是通过一个“间隔”来选择元素。例如，当间隔为 I 时，每个子集的元素之间相隔 I 个位置。
这种做法的优势在于：能更快速地将远离正确位置的元素“跳跃式”地移动到大致正确的位置，从而减少后续排序所需的操作次数。
2.2 示例说明
假设我们有一个未排序数组，共 9 个元素：
我们使用间隔为 3 和 1 来进行排序。
第一次排序时，数组被划分为 3 个子集，每个子集包含 3 个元素（颜色相同表示同一子集）：
完成第一次排序后，数组变为：
此时虽然数组仍未完全有序，但大部分元素已接近其最终位置。
最后一次排序使用间隔为 1，即标准的插入排序：
此时所需移动操作比一开始就直接使用插入排序要少得多。
2.3 如何选择间隔序列
Shell 排序的性能很大程度上取决于所使用的间隔序列。常见的间隔序列包括：
- Shell 原始序列：
N/2, N/4, ..., 1 - Hibbard 序列
- Sedgewick 序列
- Pratt 序列
选择间隔时要避免间隔太少（效率低）或太多（开销大）。具体选择可参考维基百科的 Gap Sequences 列表。
3. Java 实现
我们以 Shell 原始建议的间隔序列为例：N/2, N/4, ..., 1
实现代码如下：
public void sort(int arrayToSort[]) {
int n = arrayToSort.length;
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int key = arrayToSort[i];
int j = i;
while (j >= gap && arrayToSort[j - gap] > key) {
arrayToSort[j] = arrayToSort[j - gap];
j -= gap;
}
arrayToSort[j] = key;
}
}
}
✅ 说明：
- 外层
for循环控制间隔的递减（从N/2到1） - 内层
for循环对每个间隔进行插入排序 - 插入排序部分与标准插入排序类似，只是每次比较的是相隔
gap的元素
3.1 单元测试
我们可以使用 JUnit 编写一个简单的测试用例：
@Test
void givenUnsortedArray_whenShellSort_thenSortedAsc() {
int[] input = {41, 15, 82, 5, 65, 19, 32, 43, 8};
ShellSort.sort(input);
int[] expected = {5, 8, 15, 19, 32, 41, 43, 65, 82};
assertArrayEquals("the two arrays are not equal", expected, input);
}
4. 时间复杂度分析
Shell 排序的性能取决于所使用的间隔序列。以下是常见情况下的复杂度分析：
| 情况 | 时间复杂度 | 说明 |
|---|---|---|
| 最坏情况 | O(n²) | 当使用 Shell 原始间隔序列时 |
| 最好情况 | O(n log n) | 使用更优的间隔序列时 |
| 平均情况 | O(n^(1.5)) 左右 | 一般表现良好 |
| 空间复杂度 | O(1) | 原地排序，仅使用常数级额外空间 |
⚠️ 注意：虽然理论上最坏情况为 O(n²)，但在实际应用中，Shell 排序通常比普通插入排序快很多，尤其适用于中等规模的数据集。
5. 小结
本文介绍了 Shell 排序算法的原理、实现方式及其性能特点。
Shell 排序通过“跳跃式”插入排序的方式，显著提升了插入排序的效率。虽然其复杂度依赖于间隔序列，但实际表现非常不错，尤其适合中等规模的数据排序。
完整源码可参考 GitHub 仓库。