希尔排序算法实例讲解_十大算法排名

希尔排序算法实例讲解_十大算法排名一、什么是希尔排序1.概念希尔排序(ShellSort)是把记录按下标的一定增量分组,对每组使用插入排序算法,随着增量逐渐减少,每组包含的元素越来越多,当增量减至1时,所有元素被分为一组,算法终止2.算法原理这是一个无序数列:1、5、8、4、7、2、6、3,我们要将它按从小到大排序。按照希尔排序的思想,我们先把数列进行分组排序首先,我们选择序列长度的一半4,作为增量进行分组如果所示,1和7一组,5和2一组,8和6一组,4和3一组,共四组然后,我们对每一组进行插入排序,排序后序列如下经

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

十大经典排序算法

一、什么是希尔排序

1.概念

希尔排序(Shell Sort)是把记录按下标的一定增量分组,对每组使用插入排序算法,随着增量逐渐减少,每组包含的元素越来越多,当增量减至1时,所有元素被分为一组,算法终止

2.算法原理

这是一个无序数列:1、5、8、4、7、2、6、3,我们要将它按从小到大排序。按照希尔排序的思想,我们先把数列进行分组排序
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3mJDYTFM-1591770808598)(./希尔1.png)]
首先,我们选择序列长度的一半4,作为增量进行分组
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zSodnhEj-1591770808600)(./希尔2.png)]
如果所示,1和7一组,5和2一组,8和6一组,4和3一组,共四组

然后,我们对每一组进行插入排序,排序后序列如下
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-e1U9xjSX-1591770808601)(./希尔3.png)]
经过这一轮排序,序列有序了很多,接着我们进一步缩小增量,增量缩小为原来的一半,也就是2,再进行分组排序
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-g0AXx9M0-1591770808602)(./希尔4.png)]
如图所示,1、6、7、8一组,2、3、5、4一组,共两组

我们再对每一组进行插入排序,排序后序列如下
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dVZQ7HZY-1591770808604)(./希尔5.png)]
最后,我们进一步把增量缩小为原来一半,也就是1,这相当于直接在序列上进行插入排序,排序结果如下
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0x3LrwTY-1591770808607)(./希尔6.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);

Jetbrains全家桶1年46,售后保障稳定

二、希尔排序算法特点

1.时间复杂度

希尔排序算法利用分组粗调的方式减少了插入排序算法的工作量,使得算法的平均复杂度低于O(N^2)

但某些极端的情况下,希尔排序算法的时间复杂度仍然是O(N^2),甚至比插入排序算法更慢
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EO2azRMG-1591770808608)(./希尔7.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)]
上图例子中,绿色5在紫色5之前,但经过希尔排序之后,绿色5在紫色5之后,所以希尔排序是一种不稳定排序算法

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/215565.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 知乎收藏数最高的1000个回答

    掃描了知乎兩千五百萬篇答案,統計出了“收藏數”最高的1000篇:同系列一:知乎收藏数最高的1000个回答-陈鹏举的文章-知乎专栏同系列二:知乎关注人数最高的1000个问题-陈鹏举的文章-知乎专栏同系列三:知乎关注人数最高的1000个收藏夾-陈鹏举的文章-知乎专栏同系列四:知乎关注人数最高的1000个專欄-陈鹏举的文章-知乎专栏哪些知识技能一定

  • 一脸懵逼学习Nginx及其安装,Tomcat的安装

    一脸懵逼学习Nginx及其安装,Tomcat的安装

  • list去重 distinct

    list去重 distinct总结下。1.使用java8新特性stream进行List去重publicstaticList<String>delRepeat(List<String>list){List<String>myList=listAll.stream().distinct().collect(Collectors.toList());returnmyList;}2.双重for循环去重(不推荐使用,速度太慢)实际是使用lis…

  • uefi shell 修复引导_磁盘主引导损坏怎么办

    uefi shell 修复引导_磁盘主引导损坏怎么办1、 红旗DC5.032bit莫名其妙死机,(服务器是ibmx36502008年左右的机器),硬重启后无法启动,极其缓慢,到最后报错:a)        Init:cannotexecute“etc/rc.d/rc”b)       各种初始化失败,root卷组无法挂载;c)        服务器四块盘,只有一块不停地闪烁,其他几乎没有响应;d)       初步判断,

  • Intellij IDEA 查找接口实现类的快捷键「建议收藏」

    Intellij IDEA 查找接口实现类的快捷键「建议收藏」查找接口的实现类:IDEA风格ctrl+alt+B在按F2查看详细文档注解查看类或接口的继承关系:ctrl+h1、IDEA_查找接口的实现的快捷键 个人分类管理http://blog.csdn.net/u010003835/article/details/790366662、intellijidea8.1.2中找到实现一个类或者接口子类的快捷键 https://zhidao.ba…

  • pycharm设置项目编码「建议收藏」

    pycharm设置项目编码「建议收藏」pycharm设置项目编码1.pycharm-file-setting2.Editor-FileEncodings3.选择自己想要的编码4.点击确定

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号