【希尔排序算法】详解：原理、实现与优化
【希尔排序算法】详解：原理、实现与优化
🌺The Begin🌺点点关注，收藏不迷路🌺 |
一、算法概述
希尔排序(Shell Sort)是Donald Shell于1959年提出的一种改进的插入排序算法，又称缩小增量排序。它通过将原始数组分解为若干个子序列进行插入排序，随着增量逐渐减小，最终对整个数组进行一次插入排序。
基本特性
- 时间复杂度：取决于增量序列，通常为O(n^(1.3-2))
- 空间复杂度：O(1)（原地排序）
- 稳定性：不稳定排序算法
- 适用场景：中等规模数据，特别是部分有序的数据
二、算法原理详解
核心思想
- 分组插入排序：按照增量gap将数组分为若干子序列
- 逐步缩小增量：每次缩小gap值，直到gap=1
- 最终插入排序：当gap=1时，就是标准的插入排序
增量序列选择
常用的增量序列：
- Shell原始序列：gap = n/2, n/4, …, 1
- Hibbard序列：1, 3, 7, …, 2^k-1
- Sedgewick序列：1, 5, 19, 41, 109,…
三、算法流程图示
示例数组：[8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
初始状态
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐ │ 8 │ 9 │ 1 │ 7 │ 2 │ 3 │ 5 │ 4 │ 6 │ 0 │ └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘ 第一轮：gap=5
将数组分为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 │ └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘ 第二轮：gap=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 │ └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘ 第三轮：gap=1（标准插入排序）
最终排序结果： ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘ 四、完整Java实现
packagecom.kwan.springbootkwan.controller;publicclassShellSort{/** * 基础希尔排序（使用Shell原始增量序列） * @param arr 待排序数组 */publicstaticvoidshellSort(int[] arr){if(arr ==null|| arr.length <=1){return;}int n = arr.length;// 初始gap为数组长度的一半，逐步缩小gap直到1for(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;}}}// 测试代码publicstaticvoidmain(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);}// 打印数组privatestaticvoidprintArray(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(1)
稳定性
希尔排序是不稳定的排序算法，因为相同的元素可能会被分到不同的子序列中，导致相对顺序改变。
六、实际应用场景
- 中等规模数据排序：当数据量在几千到几万时，希尔排序表现良好
- 嵌入式系统：由于空间复杂度低，适合资源受限的环境
- 作为更复杂算法的预处理步骤：可以先使用希尔排序进行部分排序
七、与其他排序算法的对比
| 算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 希尔排序 | 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序列在实践中表现良好。希尔排序的实现简单，空间效率高，是值得掌握的经典排序算法之一。
🌺The End🌺点点关注，收藏不迷路🌺 |
