Javajava算法
希尔排序算法详解：原理、实现与优化
希尔排序是一种改进的插入排序算法，通过分组和缩小增量逐步完成排序。其时间复杂度取决于增量序列选择，通常为 O(n^1.3 至 n^2)，空间复杂度为 O(1)。该算法不稳定，适用于中等规模数据及部分有序数据的排序场景。相比快速排序和归并排序，它在资源受限环境下具有优势。选择合适的增量序列对性能至关重要，Hibbard 序列和 Sedgewick 序列在实践中表现良好。
希尔排序是一种改进的插入排序算法，通过分组和缩小增量逐步完成排序。其时间复杂度取决于增量序列选择，通常为 O(n^1.3 至 n^2)，空间复杂度为 O(1)。该算法不稳定，适用于中等规模数据及部分有序数据的排序场景。相比快速排序和归并排序，它在资源受限环境下具有优势。选择合适的增量序列对性能至关重要，Hibbard 序列和 Sedgewick 序列在实践中表现良好。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
希尔排序 (Shell Sort) 是 Donald Shell 于 1959 年提出的一种改进的插入排序算法，又称缩小增量排序。它通过将原始数组分解为若干个子序列进行插入排序，随着增量逐渐减小，最终对整个数组进行一次插入排序。
常用的增量序列：
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 8 │ 9 │ 1 │ 7 │ 2 │ 3 │ 5 │ 4 │ 6 │ 0 │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
将数组分为 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 │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
将数组分为 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 │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
最终排序结果：
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
public class ShellSort {
/**
* 基础希尔排序（使用 Shell 原始增量序列）
* @param arr 待排序数组
*/
public static void shellSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int n = arr.length;
// 初始 gap 为数组长度的一半，逐步缩小 gap 直到 1
for (int gap = n / 2; gap > 0; gap /= 2) {
// 从第 gap 个元素开始，对各个子序列进行插入排序
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;
}
}
}
// 测试代码
public static void main(String[] args) {
int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
System.out.println("原始数组:");
printArray(arr);
System.out.println("\n希尔排序后:");
shellSort(arr);
printArray(arr);
}
// 打印数组
private static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}
希尔排序的时间复杂度取决于增量序列的选择：
| 增量序列 | 最坏时间复杂度 | 平均时间复杂度 |
|---|---|---|
| Shell 原始序列 | O(n²) | O(n^(1.5)) |
| Hibbard 序列 | O(n^(3/2)) | O(n^(5/4)) |
| Sedgewick 序列 | O(n^(4/3)) | O(n^(7/6)) |
希尔排序是不稳定的排序算法，因为相同的元素可能会被分到不同的子序列中，导致相对顺序改变。
| 算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 希尔排序 | O(n^(1.3-2)) | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 快速排序 | O(nlogn) | O(n²) | O(logn) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(n) | 稳定 |
希尔排序通过分组插入排序的思想，有效减少了数据移动的次数，是对简单插入排序的重要改进。虽然其时间复杂度理论分析较为复杂，但在实际应用中，特别是中等规模数据的排序场景下，希尔排序往往能提供不错的性能表现。
选择合适的增量序列对希尔排序的性能至关重要，Hibbard 序列和 Sedgewick 序列在实践中表现良好。希尔排序的实现简单，空间效率高，是值得掌握的经典排序算法之一。