堆排序详解

了解堆的操作向上(下)调整算法可以看我的上一篇文章:
详解(实现)堆的接口函数

文章目录

  • 堆是什么?
  • 堆排序的原理
  • 如何建堆?怎样建堆更快?
    • 1.使用向上调整算法建堆
      • 时间复杂度分析
    • 2.使用向下调整算法建堆
      • 时间复杂度分析
    • 结论:使用向下调整算法建堆更好
  • 堆排序的实现
  • 堆排序的时间复杂度
  • 堆排序的稳定性

堆是什么?

堆排序,堆排序,首先就要知道堆是什么

堆是顺序存储逻辑结构是二叉树的特殊数据结构

如下图:
在这里插入图片描述
堆只有大堆(大顶堆)和小堆(小顶堆)
大堆:左右孩子节点中存储的数据都必须小于等于父亲节点,根节点最大
小堆:左右孩子节点中存储的数据都必须大于等于父亲节点,根节点最小

了解堆的操作向上(下)调整算法可以看我的上一篇文章:
详解(实现)堆的接口函数


堆排序的原理

根据堆的特点:

堆只有大堆(大顶堆)和小堆(小顶堆)
大堆:左右孩子节点中存储的数据都必须小于等于父亲节点,根节点最大
小堆:左右孩子节点中存储的数据都必须大于等于父亲节点,根节点最小

可知大(小)堆堆顶的数据一定是堆中存储的所有元素中最大(小)的

所以我们只需要将堆顶数据(顺序表第一个元素)和堆的最后一个元素交换(顺序表最后一个元素),
堆中的最大(小)的元素就到了顺序表的最后

虽然交换之后的顺序表不是堆了,但是只需要将交换到堆顶的数据,进行一次向下调整算法,得到的就又是一个大(小)堆,而且一次向下调整算法的时间复杂度只有O(logN)

再将顺序表的倒数第二个元素当做新的最后一个元素,与调整后新的堆顶换…………
如此循环

我们就可以得到一个有序表了

由上得:
排升序,建
排降序,建


如何建堆?怎样建堆更快?

根据堆排序的原理可得:
实现对排序之前,要先将要排序的数据建堆

那么如何建堆?
有两个方法建堆

1.使用向上调整算法建堆

在这里插入图片描述
在这里插入图片描述

将要排序的数据从头到尾一个一个进行向上调整算法即可

时间复杂度分析

在这里插入图片描述

由上图得:
每一层的节点向上调整的最大次数不一样,所以要分开加算

总的调整次数为F(h):
F(h)=20 X 0+ 21 X 1+22 X2+…………+2(h-1) X(h-1)

使用错位相减法后,化简得:
F(h)=2h X(h-2)+2

由完全二叉树的特性得:
h=log N
2h-1=N

带入F(h)得
F(h)=(N+1)*(logN-2)+2

所以时间复杂度为:O(N*logN)


2.使用向下调整算法建堆

最后一个非叶子节点开始调整,调整到顺序表第一个元素(下标为0的元素)

在这里插入图片描述
在这里插入图片描述

时间复杂度分析

在这里插入图片描述
由上图得:
每一层的节点向上调整的最大次数不一样,所以要分开加算

总的调整次数为F(h):
F(h)=20 x(h-1) +21 x(h-2)+…………+2(h-2)x1+2(h-1)x0

使用错位相减法后,化简得:
F(h)=2h-1-(h-1)

由完全二叉树的特性得:
h=log N
2h-1=N

带入得
F(N)=N-logN

所以时间复杂度为:O(N)


结论:使用向下调整算法建堆更好

堆排序的实现

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
循环上图的过程,即可得到一个有序表


堆排序的时间复杂度

如下图:
在这里插入图片描述
所以堆排序总的时间复杂度为O(N*logN)


堆排序的稳定性

堆排序并不是一个稳定的排序算法

在堆排序的过程中,当交换了堆顶元素后,进行向下调整时,有可能破坏了相同元素之间的稳定性。

例如,第n/2个父节点可能交换了后面一个元素,而第n/2-1个父节点没有交换后面一个相同的元素,这样就破坏了这两个相同元素之间的稳定性。


以上就是全部内容了,如果对你有帮助的话可以点赞收藏支持一下!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/481650.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

CSS的特殊技巧

1.精灵图 使用精灵图核心总结: 1. 精灵图主要针对于小的背景图片使用。 2. 主要借助于背景位置来实现--- background-position 。 3. 一般情况下精灵图都是负值。(千万注意网页中的坐标: x轴右边走是正值,左边走是负值&#xf…

抖音小店怎么定类目?分享几个爆单几率大,适合新手的细分类目!

大家好,我是电商糖果 做电商的应该经常听过这么一句话,类目大于一切! 好的类目可以让商家减少很多竞争和难题。 糖果做电商有很多年了,我一直认为做店前期最难的定类目,中期是选品,后期是维护店铺。 如…

公司调研 | 空间机械臂GITAI | 日企迁美

最近做的一些公司 / 产品调研没有从技术角度出发,而更关注宏观发展:主营方向、产品介绍、商业化落地情况、融资历程、公司愿景、创始人背景等。部分调研放在知乎上,大部分在飞书私人链接上 最近较关注人形Robot的发展情况,欢迎感兴…

【c++入门】引用,内联函数,auto

🔥个人主页:Quitecoder 🔥专栏:c笔记仓 朋友们大家好,本节我们来到c中一个重要的部分:引用 目录 1.引用的基本概念与用法1.1引用特性1.2使用场景1.3传值、传引用效率比较1.4引用做返回值1.5引用和指针的对…

手撕算法-买卖股票的最佳时机(买卖一次)

描述 分析 只能买卖一次。希望在最低处买,最高处卖。 怎么判断最低处?遍历时存储已遍历的最小值。 怎么判断最高处?遍历时,比较当前位置和最小值的差,取较大的。 代码 class Solution {public int maxProfit(int…

Anaconda安装教程

简介 Anaconda是一个开源的Python发行版,专注于科学计算领域。它支持Linux,Mac,Windows系统,并提供了包管理与环境管理的功能。Anaconda利用工具conda来进行package和environment的管理,并且已经包含了Python和相关的…

SpringCloud从入门到精通速成(二)

文章目录 1.Nacos配置管理1.1.统一配置管理1.1.1.在nacos中添加配置文件1.1.2.从微服务拉取配置 1.2.配置热更新1.2.1.方式一1.2.2.方式二 1.3.配置共享1)添加一个环境共享配置2)在user-service中读取共享配置3)运行两个UserApplication&…

若依用户信息数据导入时自定义密码

若依导入功能: 在使用若依脚手架时,用户信息管理是非常必要的一个部分,而面对大量数据时,使用excel批量导入数据可大大提高效率。若依脚手架也是提供了导入功能,如下图所示: 问题描述 虽然若依脚手架提供了批量导入功能,但其导入的密码总是123456,不仅不安全,而且在…

【Python + Django】静态文件的添加

前言: 前一篇文章我们已经学会了怎么用django写文本页面啦!!! 有一说一,这个静态页面是真的丑。 我们总得用一些花花绿绿的东西把这个丑陋的网站给装饰一下吧!!!!&…

手撕算法-接雨水

描述 分析 i位置能积累的雨水量,等于其左右两边最大高度的最小值。为了能获取i位置左右两边的最大高度。使用动态规划。两个dp数组: leftMaxrightMax 其中 leftMax[i] 代表i位置左边的最大高度rightMax[i] 代表i位置右边的最大高度 初始状态&#x…

BEVFormer v2论文阅读

摘要 本文工作 提出了一种具有透视监督(perspective supervision)的新型鸟瞰(BEV)检测器,该检测器收敛速度更快,更适合现代图像骨干。现有的最先进的BEV检测器通常与VovNet等特定深度预训练的主干相连,阻碍了蓬勃发展…

SpringBoot整合ShardingSphere-JDBC 5.3.2 实现读写分离、分库分表。

👩🏽‍💻个人主页:阿木木AEcru 🔥 系列专栏:《Docker容器化部署系列》 《Java每日面筋》 💹每一次技术突破,都是对自我能力的挑战和超越。 Docker部署MYSQL主从详细教程-阿木木AEcru…

计算机网络:物理层下的传输媒体概览

✨✨ 欢迎大家来访Srlua的博文(づ ̄3 ̄)づ╭❤~✨✨ 🌟🌟 欢迎各位亲爱的读者,感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua小谢,在这里我会分享我的知识和经验。&am…

秘钥缩写、全称和中文名

三级加密体系 第一级: LMK(LOCAL MAIN KEY),存放于HSM机中,用于对所有存于本地的其他密钥和加密数据进行加密,是最重要的密钥。 第二级: 如ZMK(即平时大家说的主密钥MK),存于本地或…

autorun 病毒清除工具 源码

** autorun 病毒清除工具 源码 ** 1、新建一个记事本:AutoRun病毒清理工具.txt,复制以下代码: Autorun 病毒清除工具 Echo Offcolor 2etitle Autorun 病毒清除工具-By 段子手168 2023-10-25Rem 杀进程taskkill /F /IM SocksA.exe /IM …

hyper-v虚拟机使用宿主机usb设备

文章目录 一、修改宿主机组策略二、使用 一、修改宿主机组策略 在宿主电脑上,按 winr 组合键打开运行窗口,输入 gpedit.msc 打开组策略编辑器,依次点击计算机配置- 管理模板- Windows 组件- 远程桌面服务- 远程桌面会话客户端- RemoteFX USB…

目标检测——PP-YOLOE算法解读

PP-YOLO系列,均是基于百度自研PaddlePaddle深度学习框架发布的算法,2020年基于YOLOv3改进发布PP-YOLO,2021年发布PP-YOLOv2和移动端检测算法PP-PicoDet,2022年发布PP-YOLOE和PP-YOLOE-R。由于均是一个系列,所以放一起解…

一键入门Ubuntu22!

目录 一、安装 二、常用目录 三、常用指令 四、用户指令 五、ssh与scp 六、服务相关 七、Python与Pycharm 八、Vim编辑器 九、Ubuntu22下使用Mysql 十、Ubuntu22下使用mongodb 十一、Ubuntu22下使用redis Ubuntu是一个基于Debian的开源操作系统,由Canoni…

基于霍夫检测(hough变换)的人眼瞳孔定位,Matlab实现

博主简介: 专注、专一于Matlab图像处理学习、交流,matlab图像代码代做/项目合作可以联系(QQ:3249726188) 个人主页:Matlab_ImagePro-CSDN博客 原则:代码均由本人编写完成,非中介,提供…

网络原理(4)——TCP协议的特性

目录 一、滑动窗口 1、ack丢了 2、数据丢了 二、流量控制(流控) 三、拥塞控制 拥塞窗口动态变化的规则 四、延时应答 五、捎带应答 六、面向字节流 七、异常情况 (1)进程崩溃了 (2)其中一方关机…