大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全家桶1年46，售后保障稳定
十大经典排序算法
- 十大经典排序算法-冒泡排序算法详解
- 十大经典排序算法-选择排序算法详解
- 十大经典排序算法-插入排序算法详解
- 十大经典排序算法-希尔排序算法详解
- 十大经典排序算法-快速排序算法详解
- 十大经典排序算法-归并排序算法详解
- 十大经典排序算法-堆排序算法详解
- 十大经典排序算法-计数排序算法详解
- 十大经典排序算法-桶排序算法详解
- 十大经典排序算法-基数排序算法详解
一、什么是希尔排序
1.概念
希尔排序（Shell Sort）是把记录按下标的一定增量分组，对每组使用插入排序算法，随着增量逐渐减少，每组包含的元素越来越多，当增量减至1时，所有元素被分为一组，算法终止
2.算法原理
这是一个无序数列：1、5、8、4、7、2、6、3，我们要将它按从小到大排序。按照希尔排序的思想，我们先把数列进行分组排序
![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3mJDYTFM-1591770808598)(./希尔1.png)]](https://img-blog.csdnimg.cn/20200610143351745.png)
![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3mJDYTFM-1591770808598)(./希尔1.png)]](https://javaforall.net/wp-content/uploads/2020/11/2020110817443450.jpg)
首先，我们选择序列长度的一半4，作为增量进行分组
![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zSodnhEj-1591770808600)(./希尔2.png)]](https://img-blog.csdnimg.cn/20200610143410549.png)
如果所示，1和7一组，5和2一组，8和6一组，4和3一组，共四组
然后，我们对每一组进行插入排序，排序后序列如下
![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-e1U9xjSX-1591770808601)(./希尔3.png)]](https://img-blog.csdnimg.cn/20200610143427577.png)
经过这一轮排序，序列有序了很多，接着我们进一步缩小增量，增量缩小为原来的一半，也就是2，再进行分组排序
![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-g0AXx9M0-1591770808602)(./希尔4.png)]](https://img-blog.csdnimg.cn/20200610143447219.png)
如图所示，1、6、7、8一组，2、3、5、4一组，共两组
我们再对每一组进行插入排序，排序后序列如下
![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dVZQ7HZY-1591770808604)(./希尔5.png)]](https://img-blog.csdnimg.cn/20200610143508293.png)
最后，我们进一步把增量缩小为原来一半，也就是1，这相当于直接在序列上进行插入排序，排序结果如下
![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0x3LrwTY-1591770808607)(./希尔6.png)]](https://img-blog.csdnimg.cn/20200610143528351.png)
至此所有的元素都是有序的
3.算法实现
function sort(arr) {
// 希尔排序的增量
let d = arr.length;
while (d > 1) {
// 使用希尔增量的方式，每次折半
d = parseInt(d / 2);
for (let x = 0; x < d; x++) {
for (let i = x + d; i < arr.length; i = i + d) {
let temp = arr[i];
let j;
for (j = i - d; j >= 0 && arr[j] > temp; j = j - d) {
arr[j + d] = arr[j];
}
arr[j + d] = temp;
}
}
}
}
let arr = [1, 5, 8, 4, 7, 2, 6, 3];
sort(arr);
console.log(arr);
二、希尔排序算法特点
1.时间复杂度
希尔排序算法利用分组粗调的方式减少了插入排序算法的工作量，使得算法的平均复杂度低于O(N^2)
但某些极端的情况下，希尔排序算法的时间复杂度仍然是O(N^2)，甚至比插入排序算法更慢
![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EO2azRMG-1591770808608)(./希尔7.png)]](https://img-blog.csdnimg.cn/20200610143557724.png)
上图是我们刚刚希尔排序例子里，进行最后一次增量为1时排序前的序列，如果初始序列就是这个，那么前面进行的增量为4、增量为2的排序，都没有产生任何元素的交换，反而增加了分组操作的成本
为了降低希尔排序算法的时间复杂度，提出了更严谨的算法增量
- Hibbard增量，序列为：1、3、7、15…，通项公式为2^k-1， 最坏的时间复杂度为O(n^(3/2))
- Sedgewick增量，序列为：1、5、19、41、109…，通项公式为 9 * 4^k – 9 * 2^k + 1 或者 4^k – 3 * 2^k + 1，最坏的时间复杂度为O（n^(4/3)）
2.空间复杂度
希尔排序算法排序过程中需要一个临时变量存储插入元素，所需要的额外空间为1，因此空间复杂度为O(1)
3.稳定性
希尔排序算法会进行分组排序，在分组排序的过程中有可能改变相同元素的前后位置，因此是一种不稳定的排序算法
![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2zjhs2mU-1591770808610)(./希尔8.png)]](https://img-blog.csdnimg.cn/20200610143614469.png)
上图例子中，绿色5在紫色5之前，但经过希尔排序之后，绿色5在紫色5之后，所以希尔排序是一种不稳定排序算法
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/215565.html原文链接：https://javaforall.net
