1. 全栈程序员必看首页

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

全栈程序员-站长 • • 未分类 • 阅读 2

希尔排序算法实例讲解_十大算法排名一、什么是希尔排序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之后，所以希尔排序是一种不稳定排序算法

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

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/215565.html原文链接：https://javaforall.net

赞 (0)
全栈程序员-站长的头像全栈程序员-站长
0 0


相关推荐

  • 逻辑漏洞之越权、支付漏洞「建议收藏」

    逻辑漏洞之越权、支付漏洞「建议收藏」

    逻辑漏洞之越权、支付漏洞「建议收藏」目录逻辑漏洞Web安全渗透三大核心方向输入输出登录体系、权限认证业务逻辑漏洞分类1、登录体系安全暴力破解cookie安全加密测试登录验证绕过任意注册2、业务一致性安全手机号篡改邮箱和用户名更改订单ID更改商品编号更改用户ID篡改流程顺序3、业务数据篡改金额数据篡改商品数量篡改最大数限制突破金额&优惠组合修改4、密码找回漏洞分析数据包，定位敏感信息分析找回机制修改数据包验证任意密码找回5、验证码突破暴力破解时间、次数突破回显测试验证码绕过测试验证检验机制猜解6、会话权限安全未授权访问水平&垂直

    全栈程序员-站长的头像 全栈程序员-站长
    2022年6月14日
    39
  • Dubbo负载均衡策略之最小活跃策略

    Dubbo负载均衡策略之最小活跃策略

    Dubbo负载均衡策略之最小活跃策略今天我来学习一下Dubbo负载均衡之一的最小活跃策略-LeastActiveLoadBalance首先，让我们对负载均衡做一个简单的介绍。所谓集负载均衡，其含义就是指将负载（工作任务）进行平衡、分摊到多个操作单元上进行运行。负载均衡、集群容错、服务降级这三个概念在微服务中非常重要。从调用顺序来看，一次完整的RPC调用首先是负载均衡、其次是集群容错、最后是服务降级：负载均衡解决了选哪一个的问题、集群容错解决了换哪一个的问题、而服务降级则是解决了全错了怎么办的问题今天我们要学习的策略是最小活跃策略-Le

    全栈程序员-站长的头像 全栈程序员-站长
    2022年7月11日
    19
  • nginx简单配置多个server

    nginx简单配置多个server

    nginx简单配置多个server1：安装nginx步骤就不说了，自行百度。2：打开nginx的配置文件nginx.conf这是项目1的配置，现在需要再开个同域名不同端口的项目，如下图：注意：LZ一直出现访问不了，折腾了许久，是因为服务器www.pigaudio.com或120.77.223.7只开了默认的80端口，而8088端口并未开，所以只需要登陆你的服务账号添加一个8088即可，比如你的服务器是阿里云购买的，则需要登陆阿里…

    全栈程序员-站长的头像 全栈程序员-站长
    2025年6月16日
    3
  • 测试用例_因果图_测试用例图

    测试用例_因果图_测试用例图

    测试用例_因果图_测试用例图因果图法一、应用场合​ 界面中有多个控件，控件之间有组合或者限制关系，为了弄清楚不同的输入组合会对应怎样不同的输出结果，可以使用因果图或判定表法。【说明】因果图/判定表法比较适合测试组合数量少（一般指20种以下）的情况（如果组合数量大可以选择使用正交排列法效率会更高）二、因果图法2.1解析因果图法​ 因（原因)：输入条件​ 果（结果）：输出结果​ 因果图：通过画图的方式说明输入条件和输出结果之间的关系。2.2图形符号（1）基本图形符合——表达的是因和果之间的关系恒等如果

    全栈程序员-站长的头像 全栈程序员-站长
    2022年8月14日
    8
  • 正态分布方差推导_均匀分布的期望和方差公式

    正态分布方差推导_均匀分布的期望和方差公式

    正态分布方差推导_均匀分布的期望和方差公式概论：一维随机变量期望与方差二维随机变量期望与方差协方差1.一维随机变量期望与方差：公式：离散型：E(X)=∑i=1->nXiPiY=g(x)E(Y)=∑i=1->ng(x)Pi连续型：E(X)=∫-∞->+∞xf(x)dxY=g(x)E(Y)=∫-∞->+∞g(x)f(x)dx方差：D(x)=E(x²)-E²(x)标准差：根号下的方差常用分布的数学期望和方差：0~1分布…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年9月17日
    5
  • offsetWidth,clientWidth的区别

    offsetWidth,clientWidth的区别

    offsetWidth,clientWidth的区别offsetWidth offsetHeight ，offsetLeft offsetTopscrollWidth scrollHeight ，scrollLeft scrollTopclientWidth clientHeight 对象的实际宽度和高度      offsetWidth，offsetHeight  offsetWidth=width+padd

    全栈程序员-站长的头像 全栈程序员-站长
    2022年7月22日
    8

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

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