(Java)算法学习(四): 希尔排序-排序过程拆解与算法优化

始:希尔排序的简单介绍

希尔排序（Shell Sort）是一种基于插入排序的改进算法，由Donald Shell于1959年提出。它通过将原始列表分割成多个子序列进行插入排序，逐步缩小子序列的间隔，最终完成整体排序。希尔排序的核心思想是减少逆序对，从而提升排序效率。

1.算法原理

希尔排序通过定义一个间隔序列（Gap Sequence）来划分子序列。初始间隔较大，逐步缩小至1（即普通的插入排序）。每次按当前间隔分组后，对每组进行插入排序。随着间隔减小，列表逐渐趋于有序，最终完成排序。

2.间隔序列选择

间隔序列的选择直接影响算法效率。常见选择包括：

• Shell原始序列：$gap = \\frac{n}{2}, \\frac{n}{4}, \\ldots, 1$（逐步折半）。
• Hibbard序列：$gap = 2^k – 1$（如1, 3, 7, 15…），时间复杂度可优化至$O(n^{3/2})$。

3.时间复杂度

• 最坏情况：取决于间隔序列，一般为$O(n^2)$。
• 最佳情况：$O(n \\log n)$（如使用Sedgewick序列）。

4.优缺点

• 优点：比简单插入排序高效，尤其对中等规模数据表现良好。
• 缺点：时间复杂度不稳定，依赖间隔序列的选择；不适合大规模数据。

一.文字描述流程

步长序列决定时间复杂度 希尔排序的时间复杂度取决于步长序列的选择。常见序列包括希尔增量序列（O(n²)）和更优的Hibbard序列（O(n^1.5)）。

排序过程示例:

以数组 [2, 8, 9, 4, 7, 9, 6, 12] 为例：

初始步长 i=4 分组：

• 组1: 2, 7
• 组2: 8, 9
• 组3: 9, 6
• 组4: 4, 12

插入排序后：

• 组1: 2, 7
• 组2: 8, 9
• 组3: 6, 9
• 组4: 4, 12

步长 i=2 分组：

• 组1: 2, 9, 7, 6
• 组2: 8, 4, 9, 12

插入排序后：

• 组1: 2, 6, 7, 9
• 组2: 4, 8, 9, 12

步长 i=1 分组：

• 组1: 2, 4, 6, 8, 7, 9, 9, 12

插入排序后：

• 最终结果: [2, 4, 6, 7, 8, 9, 9, 12]

二.代码实现

        希尔排序中应用到了插入排序，所以要针对希尔排序的特性来对之前所介绍的“无监督插入排序”来进行一定的修改。

以下是使用了希尔序列的希尔排序本体:

//应用希尔序列的希尔排序本体
static void sell_sort(int[] arr, int arrLength) {
//序列:这里使用希尔序列 -> 希尔增量序列
/*希尔增量序列[O(n^2)]: n/2 n/4 n/8 n/16*/
//定义步长k 以及 步step
int k = 2, step;
//外部分组
do {
//获得步 -> 即分为了几组
step = (arrLength / k == 0) ? 1 : (arrLength / k);
//每一组都做插入排序
for (int i = 0; i < step; i++) {
/////无监督的插入排序/////////////////////////////////////
sell_unguarded_insert_sort(arr, i, arrLength, step);
///////////////////////////////////////////////////////
}
k *= 2;
} while (step != 1);
}

以下是针对希尔排序改进的无监督插入排序:

        希尔排序下的无监督插入排序，由于选取元素是按照步长长度来跳跃式选取的，所以在初始化以及迭代数据的时候要将原本的+1改变为+step(步长)，相应的-1也应改为 -step。

//希尔排序下的插入排序 -> 根据步长来跳跃式选取元素
//传入: arr数组, 起始元素下标(0,1,2…..step-1), arrLength数组长度, step步长
static void sell_unguarded_insert_sort(int[] arr, int i, int arrLength, int step) {
int minIndex = i;
//找最小值的下标
for (int j = i + step; j < arrLength; j += step) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
//最小值前置
while (minIndex > i) {
MyMath.swap(arr, minIndex, minIndex – step);
minIndex -= step;
}
//排序
for (int j = i + step * 2; j < arrLength; j += step) {
int k = j;
while (arr[k] < arr[k – step]) {
MyMath.swap(arr, k, k – step);
k -= step;
}
}
}

三.代码优化

希尔排序的核心就是： 步长序列

希尔排序的时间复杂度是可变的(重要!)

希尔排序的时间复杂度与步长序列有关，所以改变步长序列就会改变希尔排序的时间复杂度，优化步长序列就会优化希尔排序的运行速度！

优化: 使用更加优秀的“Hibbard增量序列”

        希尔增量序列:  n/2 n/4 n/8 n/16            -> 时间复杂度: o(n^2)

        Hibbard增量序列: 1 3 7 ….. 2^(k-1)        -> 时间复杂度:o(n^1.5)

代码如下：

//应用Hibbard增量序列的希尔排序本体
static void sell_sort_hibbard(int[] arr, int arrLength) {
//序列:这里使用Hibbard增量序列
/*(相比希尔序列更优秀)Hibbard增量序列[O(n^1.5)]: 1 3 7 15 31 ….. 2^(k-1)*/
/* 规律一
* 3 = 1 * 2 + 1
* 7 = 3 * 2 + 1
* ……..
* 规律二
* 7 / 2 = 3
* 15 / 2 = 7
* */
int step = 1;
//如果step的步长大等于了数组全长的1/2 -> 那么我每一个分组都只有二个元素,即希尔增量中的 n/2
//但是Hibbard增量序列的规律导致往往找不到一个等于全长1/2的数据
//所以要将一开始的step设置为大于全长的1/2的最小规律数,再开始进行step数据的迭代,即step从多往少来
while ((step * 2 + 1) <= arrLength / 2) step = (step * 2) + 1;
do {
for (int i = 0; i < step; i++) {
sell_unguarded_insert_sort(arr, i, arrLength, step);
}
step /= 2;
} while (step > 1);
}

四.性能测试

请输入要测试的数组长度(超过10不打印):
1000
(希尔增量)运行时间:1.0ms
(Hibbard)运行时间:0.0ms

=====================================================================

请输入要测试的数组长度(超过10不打印):
10000
(希尔增量)运行时间:5.0ms
(Hibbard)运行时间:2.0ms

=====================================================================

请输入要测试的数组长度(超过10不打印):
100000
(希尔增量)运行时间:25.0ms
(Hibbard)运行时间:17.0ms

=====================================================================

请输入要测试的数组长度(超过10不打印):
1000000
(希尔增量)运行时间:157.0ms
(Hibbard)运行时间:186.0ms

=====================================================================

请输入要测试的数组长度(超过10不打印):
10000000
(希尔增量)运行时间:2408.0ms
(Hibbard)运行时间:2921.0ms

从测试数据可以看出，在不同数据规模下，Hibbard增量序列和希尔增量序列的表现存在差异：

• 小规模数据（10^3-10^5）： Hibbard增量（1, 3, 7, 15…）运行时间更短 1000元素时快1.0ms，10000元素时快3.0ms，100000元素时快8.0ms

• 大规模数据（10^6-10^7）： 希尔增量（n/2, n/4…）反超 1000000元素时快29.0ms，10000000元素时快513.0ms

1.性能差异原因

Hibbard增量在小数据量的优势： 增量序列的数学性质更优（2^k-1），能减少无效比较次数 元素移动距离更合理，数据局部有序性建立更快

希尔增量在大数据量的优势： 早期增量下降较慢（n/2开始），适合大规模数据的初始粗调 减少了大规模数据时Hibbard增量可能产生的重复子序列处理开销

2.选择建议

处理10^5以下规模数据时优先考虑Hibbard增量 处理更大规模数据时，希尔增量或Sedgewick增量可能更合适

尾.个人想说的话：         我是一名学习JAVA等编程语言的普通学生，如果我的这篇文章帮助到了你，我很开心，同时如果我的文章有问题，请各位发现后对我所说的有问题的部分做出修改和指正（请详细一些），避免他人看到造成误导，欢迎各位在评论区讨论、补充、以及纠正错误。

如果觉得博客内容对你有帮助的话可以支持一下我的其它博客：

• 上一篇：(Java)算法学习(三): 快速排序-排序过程拆解与算法优化