(超详解)堆排序+(图解)
目录:
1:如何建堆(两种方法)
2:两种方法建堆的时间复杂度分析与计算
3:不同类型的排序方式我们应该如何建堆
文章正式开始:
1:如何建堆
在实现堆排序之前我们必须得建堆,才能够实现堆排序
首先在讲解如何建堆之前让我们先来回顾一下堆的概念,堆是一种完全二叉树,它有两种形式,一种是大根堆,另外一种是小根堆。
大根堆:所有的父亲结点大于或等于孩子结点。
小根堆:所有的父亲结点小于或等于孩子结点。
本文在介绍堆排序的时候我们都默认排升序。
方法1:我们采用向上调整算法建堆
我们知道向上调整算法的前提是前面的数必须是堆,所以我们就形成了一种思路:
第一个数我们可以看成是一个堆,那么从第二个数开始我们就依次采用向上调整算法,这样最后我们的数字就会形成一个堆。
图解:
向上调整建堆的代码如下,如果不理解可以自己尝试画图:
//假设排升序,建大堆
void HeapSort(int* a, int n){//先建堆,用向上调整算法for (int i = 1; i < n; i++){AdjustUp(a, i);}}
方法2:采用向下调整的思路建堆
向下调整的前提:要调整的对象左右子树都得是堆
那么我们如何通过一个数组来原地建堆呢?
其实我们可以这样想,叶子结点既可以看作是大堆,也可以看作是小堆,所以我们可以从后面往前面来建堆。
思路:找到倒数第一个非叶子结点,这样我们可以保证左右子树都是堆,才能够对整个堆使用向下调整算法的思想。
那么最后一个非叶子结点如何才能找到呢?这里不就是我们要记住的一个特点吗,通过孩子结点来算父亲结点。
parent=(child-1)/2;
我们先找到最后一个结点的下标,然后通过结点算父亲的公式不就可以算出来了吗
所以倒数第一个非叶子结点的下标不就是 (n-1-1)/2吗 ?
图解过程:
2:两种方法建堆复杂度的分析
首先我们直接公布结论:
向上调整算法的时间复杂度为O(N*logN),向下调整算法的时间复杂度为O(N),所以建堆在复杂度的层面来说向下调整算法是优于向上调整算法的。
向上调整算法的时间复杂度分析:
我们知道向上调整算法是依次将后一个元素向上进行调整,那么最坏的情况下就是我们所插入一个数就要调整到根节点处。
同理向下调整的复杂度分析
为啥同样都是建堆的过程,可是为啥向下调整算法的时间复杂度优于向上调整算法呢
因为向下调整算法时,最后一层结点不需要向下调整,且最后一层的结点比较多,从下往上,结点个数变少,乘以的层数变多,但是主要取决于时间复杂度的是结点个数多的。
而向上调整算法,最后一层结点的个数多,且需要调整的层数也最高,导致向上调整的时间复杂度高。
3.堆排序
在讲了前面两种算法的基础上我们就可以来谈一谈我们的堆排序了,堆排序并不是我们所讲的数据结构,虽然说堆数据结构也可以看出堆的升序与降序,但是我们可能并不是只要打印这个数组出来,我们可能还会进行一些算法,比如2分查找....。
堆排序的思路:
1:首先对数组进行建堆。
2:将最后一个元素与第一个元素交换,在向下进行调整
3:循环往复的进行,最后排除来的就是我们所需要的结果了。
那我们在排升序的时候应该见建大堆,还是小堆呢?
相信许多人在看到要排升序的时候,可能第一反应的是建小堆,因为小堆中的第一个数是所有元素中最小的那个数,但是当我们建立小堆的时候,那我们的第二个小的数字如何取呢?
且当我们将第一个元素排好之后,后面的元素的关系都不对了,就会形成兄弟变父子,父子叔侄变兄弟,那么我们可能还需要建一次堆,那么总体的时间复杂度为N*(N*logN),
所以我们排升序需要建大堆,排降序需要建小堆。
而我们为什么可以这样子做呢?
我们假设有一个数组我们已近将他建成大堆了,那么我们很明显知道根节点最大,那么我们就可以这样子做。
将最大的根结点与最后一个数字进行交换,由于我们只是交换了根结点与最后一个元素,其他的结构没有动,所以就可以使用向下调整,然后在对前n-1个元素进行向下调整,整个的时间复杂度为logn。每次选一个大的,我们向将大的排在最后,循环进行就可以排成我们所需要的结果了。
代码实现
void HeapSort(int* a, int n)
{//向下调整算法建堆,建大堆,排升序for (int i = (n-1-1)/2; i >=0; i--){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}
也可以使用向上调整建堆进行堆排序:
假设排升序,建大堆
//void HeapSort(int* a, int n)
//{
// //先建堆,用向上调整算法
// for (int i = 1; i < n; i++)
// {
// AdjustUp(a, i);
// }
//
// //将最后一个数与根节点交换
// //在进行向下调整,循环执行
// int end = n - 1;
// /*while (end > 0)
// {
// Swap(&a[end], &a[0]);
// AdjustDown(a, end, 0);
// --end;
// }*/
//
//
//
//
//}
本章完!!!
感谢观看。
相关文章:

(超详解)堆排序+(图解)
目录: 1:如何建堆(两种方法) 2:两种方法建堆的时间复杂度分析与计算 3:不同类型的排序方式我们应该如何建堆 文章正式开始: 1:如何建堆 在实现堆排序之前我们必须得建堆,才能够实现堆排序 首先在讲解如何建堆之前让我们先来回顾一…...

Hadoop的YARN高可用
一、YARN简介 Hadoop2.0即第二代Hadoop,由分布式存储系统HDFS、并行计算框架MapReduce和分布式资源管理系统YARN三个系统组成,其中YARN是一个资源管理系统,负责集群资源管理和调度,MapReduce则是运行在YARN上的离线处理框架。 Y…...
C++内存检查
内存泄漏是程序中常见,也是最令人痛苦的一种bug。好在有一些检查工具可以帮助我们,这里介绍一个google 提供的简单直接的工具 Address-Sanitizer (ASAN)。 预备条件 ASAN 原来是LLVM 中的特性,后来GCC 4.8中也开始支持。也就是说࿰…...

防火墙概述及实战
目录 前言 一、概述 (一)、防火墙分类 (二)、防火墙性能 (三)、iptables (四)、iptables中表的概念 二、iptables规则匹配条件分类 (一)、基本匹配条…...

nginx代理故障总结
一、故障现象 今天公司的某个系统文件下载功能失败,报错network error,其他功能正常。 二、故障定位 首先我们检查了公司的网络情况,包括网络路由、防火墙策略、终端安全产品等,均未发现异常。 尝试访问http://X.X.X.X:7002端口&…...

python爬虫爬取电影数据并做可视化
思路: 1、发送请求,解析html里面的数据 2、保存到csv文件 3、数据处理 4、数据可视化 需要用到的库: import requests,csv #请求库和保存库 import pandas as pd #读取csv文件以及操作数据 from lxml import etree #解析html库 from …...

哈希及哈希表的实现
目录 一、哈希的引入 二、概念 三、哈希冲突 四、哈希函数 常见的哈希函数 1、直接定址法 2、除留余数法 五、哈希冲突的解决 1、闭散列 2、开散列 一、哈希的引入 顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找…...

CLIP 基础模型:从自然语言监督中学习可转移的视觉模型
一、说明 在本文中,我们将介绍CLIP背后的论文(Contrastive Language-I mage Pre-Training)。我们将提取关键概念并分解它们以使其易于理解。此外,还对图像和数据图表进行了注释以澄清疑问。 图片来源: 论文:…...
解读性能指标TP50、TP90、TP99、TP999
TP指标说明 TP指标: 指在一个时间段内,统计该方法每次调用所消耗的时间,并将这些时间按从小到大的顺序进行排序, 并取出结果为:总次数*指标数对应TP指标的值,再取出排序好的时间。 TPTop Percentile,Top百分数&#…...

【无标题】mysql 截取两个,之间字符串
截取两个,之间字符串 select area,SUBSTRING_INDEX(et.area,,,1) as XZQH1,if(length(et.area)-length(replace(et.area,,,))>1,SUBSTRING_INDEX(SUBSTRING_INDEX(et.area,,,2),,,-1),NULL) AS XZQH2,if(length(et.area)-length(replace(et.area,,,))>2,SUBS…...
全局的键盘监听事件
一、设定全局键盘监听事件 放在vue 的created()或者mounted ()中,可对整个文档进行键盘事件监听。 new Vue({ created() { window.addEventListener(keydown, this.handleKeydown); }, beforeDestroy() { window.removeEventListener(keydown, this.handleK…...

Qt自定义QSlider(支持水平垂直)
实现背景: Qt本身有自己的QSlider,为什么我们还要自定义实现呢,因为Qt自带的QSlider存在一个问题,当首尾为圆角时,滑动滚动条到首尾时会出现圆角变成矩形的问题。当然如果QSS之间的margin和滑动条的圆角控制的好的话是…...

会话控制学习
文章目录 介绍cookieexpress中使用cookie获取cookie session配置区别 介绍 cookie express中使用cookie 退出登录就是删除cookie 获取cookie 添加中间键后,直接获取 session 配置 区别...
dweb-browser阅读
dweb-browser阅读 核心模块js.browser.dwebjmm.browser.dwebmwebview.browser.dwebnativeui.browser.dweb.sys.dweb plaoc插件 核心模块 js.browser.dweb 它是一个 javascript-runtime,使用的是 WebWorker 作为底层实现。它可以让您在 dweb-browser 中运行 javasc…...
ChatGPT:使用fastjson读取JSON数据问题——如何使用com.alibaba.fastjson库读取JSON数据的特定字段
ChatGPT:使用fastjson读取JSON数据问题——如何使用com.alibaba.fastjson库读取JSON数据的特定字段 有一段Json字符串: {"code": 200,"message": "success","data": {"total": "1","l…...

2、ARM处理器概论
一、ARM处理器概述 1、ARM的含义 ARM(Advanced RISC Machines)有三种含义,一个公司的名称、一类处理器的通称、一种技术 ARM公司: 成立于1990年11月,前身为Acorn计算机公司主要设计ARM系列RISC处理器内核授权ARM内…...

【Python】福利彩票复式模拟选号程序
【效果】 【注意】 逻辑是用Random模拟10000次复试彩票选号,然后给出最大可能性一组。但是模拟终究是模拟,和现实彩票结果没有任何联系,下载下来玩就是了,没人能保证模拟出中奖号码,不要投机,不要投机! 【修改】 代码很简单,如果想改成不是复式的,自行修改即可。 如…...
Pytorch 机器学习专业基础知识+神经网络搭建相关知识
文章目录 一、三种学习方式二、机器学习的一些专业术语三、模型相关知识四、常用的保留策略五、数据处理六、解决过拟合与欠拟合七、成功的衡量标准 一、三种学习方式 有监督学习: 1、分类问题 2、回归问题 3、图像分割 4、语音识别 5、语言翻译 无监督学习 1、聚类…...
torch 和paddle 的GPU版本可以放在同一个conda环境下吗
新建conda 虚拟环境,python 版本3.8.17 虚拟机,系统centos 7,内核版本Linux fastknow 3.10.0-1160.92.1.el7.x86_64 ,显卡T4,nvidia-smi ,460.32.03,对应cuda 11.2,安装cuda 11.2和cudnn,conda…...

MYBATIS-PLUS入门使用、踩坑记录
转载: mybatis-plus入门使用、踩坑记录 - 灰信网(软件开发博客聚合) 首先引入MYBATIS-PLUS依赖: SPRING BOOT项目: <dependency><groupId>com.baomidou</groupId><artifactId>mybatis-plus…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...
docker 部署发现spring.profiles.active 问题
报错: org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习
禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

基于SpringBoot在线拍卖系统的设计和实现
摘 要 随着社会的发展,社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统,主要的模块包括管理员;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...
站群服务器的应用场景都有哪些?
站群服务器主要是为了多个网站的托管和管理所设计的,可以通过集中管理和高效资源的分配,来支持多个独立的网站同时运行,让每一个网站都可以分配到独立的IP地址,避免出现IP关联的风险,用户还可以通过控制面板进行管理功…...

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准
城市路内停车管理常因行道树遮挡、高位设备盲区等问题,导致车牌识别率低、逃费率高,传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法,正成为破局关键。该设备安装于车位侧方0.5-0.7米高度,直接规避树枝遮…...