详解希尔排序

2020年4月7日15:15:26算法评论54阅读模式

前言

当待插入元素是一个很小(当需求是从小到大排序时,从大到小排序时此处为很大)直接插入排序需要移动较多次数,性能会很差。希尔排序解决了这一问题。文章源自随机的未知-https://sjdwz.com/11140.html

基本思想

希尔排序的基本思想:
把序列按下标的一定增量分组,对每组使用直接插入排序算法排序;
随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
如果对直接插入排序不了解的朋友,可以看我的这篇文章:
https://sjdwz.com/11139.html文章源自随机的未知-https://sjdwz.com/11140.html

例子

给定数组arr为 [ 3 , 6 , 5 , 12 , 1 , 75 , 10 , -3, 0 ]
初始状态见下图:文章源自随机的未知-https://sjdwz.com/11140.html

详解希尔排序
初始序列

定义变量 h为增量,初始值为5 。文章源自随机的未知-https://sjdwz.com/11140.html

第一轮
根据增量设置成5组,颜色相同的为一组。
详解希尔排序文章源自随机的未知-https://sjdwz.com/11140.html

对每一组进行直接插入排序得到:
详解希尔排序文章源自随机的未知-https://sjdwz.com/11140.html

然后 h减半向下取整;
则 h = 3;文章源自随机的未知-https://sjdwz.com/11140.html

第二轮
根据增量设置成5组,颜色相同的为一组。文章源自随机的未知-https://sjdwz.com/11140.html

详解希尔排序
对每一组进行直接插入排序得到:文章源自随机的未知-https://sjdwz.com/11140.html

详解希尔排序
第二轮进行插入排序

然后 h减半向下取整;
则 h = 1;文章源自随机的未知-https://sjdwz.com/11140.html

第三轮
增量为1,所有序列为一组。文章源自随机的未知-https://sjdwz.com/11140.html

详解希尔排序
插入排序后得到:
详解希尔排序
h此时为1,全部有序,完毕。文章源自随机的未知-https://sjdwz.com/11140.html

由例子可知,每次都可以达到组内部分有序,大大减少了插入排序的移动开销。文章源自随机的未知-https://sjdwz.com/11140.html

代码

首先说下步长的选择:
步长的选择一般时这样的:文章源自随机的未知-https://sjdwz.com/11140.html

int h = 1;
while(h < arr.length / 2){
    h = 2 * h + 1;
}

即先把步长设置为1,只要 h 小于数组长度一半(向下取整)就在原基础上乘以2再加上1;
那么,本文的例子中的步长计算为:
初始设为1;
arr.length为9,其一半向下取整为4;
1 < 4;则 h 修正为 h = 1 * 2 + 1 = 3;
3 <4 仍成立,h修正为 h = 3 *2 + 1 = 7 。
本文一开始将 h 选为5,是为了演示方便。文章源自随机的未知-https://sjdwz.com/11140.html

根据步长分组后,进行插入排序的代码为:文章源自随机的未知-https://sjdwz.com/11140.html

for(int i= h ; i< arr.length;i++){
        value = arr[i];
        index = i - h;//初始为前一个元素
         while(index >=0 && value < arr[index]){
            //需要保证index合法
            //每当前面的元素比待插入元素大,就向后移动
            arr[index + h] = arr[index];
            //不用怕覆盖,因为value保存着待插入的值
            index -= h;
           }
           //当退出循环,表明已经找到了待插入位置,即index + h
        arr[index + h] = value;
 }

对外层循环进行解释:
i 的初始值为 h,即第一个待进行插入排序的元素的索引,i - h即为本组待插入元素的最前面元素的索引。
i++表示下一组待插入元素的索引。文章源自随机的未知-https://sjdwz.com/11140.html

内层循环就是插入排序的代码。
如果对直接插入排序不了解的朋友,可以看我的这篇文章:
https://sjdwz.com/11139.html文章源自随机的未知-https://sjdwz.com/11140.html

其他

希尔排序的时间复杂度有很多种说法,证明也比较复杂,本文不过多讨论。
关于稳定性:
在不同的插入排序过程中,相等的元素可能在各自的插入排序中发生移动,最后其前后相对位置会发生改变,所以希尔排序是不稳定的。文章源自随机的未知-https://sjdwz.com/11140.html

** 欢迎关注**

欢迎大家的关注文章源自随机的未知-https://sjdwz.com/11140.html

扫描下方的二维码关注我的微信公众号:随机的未知
详解希尔排序文章源自随机的未知-https://sjdwz.com/11140.html

文章源自随机的未知-https://sjdwz.com/11140.html
欢迎关注本站微信公众号:随机的未知 如果喜欢本文,欢迎点赞,收藏,转发,打赏。
算法最后更新:2022-2-24
  • 本文由 发表于 2020年4月7日15:15:26
  • 转载请注明:来源:随机的未知 本文链接https://sjdwz.com/11140.html
算法

详解堆排序

什么是堆 堆首先是一个完全二叉树,堆分为大顶堆和小顶堆; 大顶堆 : 每个节点的值大于或等于其左右孩子节点的值,称为大顶堆。 小顶堆同理就是每个节点的值小于或等于其左右孩子节点的值。 注意: 每个节点...
算法

详解基数排序

基本思想 基数排序的思想是将整数按位数切割成不同的数字,然后按每个位数分别比较从而得到有序的序列。 例子 本文以数组中元素均为正整数来演示思想。 给定一个数组 arr = < 6, 56, 89 , ...
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定