【数据结构初阶】堆排序
目录
前言
概念
堆排序的实现
1.建堆
(1)堆向上调整算法
(2)堆的向下调整算法
2. 利用堆删除思想来进行排序
3.堆排序的时间复杂度
4.源码
总结
前言
前边我们学习了堆的实现,对堆的每个接口都进行了详细的讲解,所以这篇文章就来看一看堆到底有哪些应用。
概念
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法:
- 大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列;
- 小顶堆:每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列;
堆排序的平均时间复杂度为 Ο(nlogn)。
我们之前学习的冒泡排序的时间复杂度为o(n^2),此处的堆排序确是Ο(nlogn),这样直接看并不能看出堆排序的优势,如果我们使用数字代入就会发现,如果我们有1000个数,进行排序时,冒泡排序是100万次,若是堆排序只需1万次,对于更大的数差别也会更大,所以堆排序是很有优势的。
堆排序的实现
1.建堆
我们根据上节课的学习,我们知道了向上调整算法和向下调整算法,他们都可以建立一个堆。
我们要切记,需要升序排列时要建一个大堆,需要降序排列时要建一个小堆。
(1)堆向上调整算法
现在我们给出一个数组,逻辑上看做一颗完全二叉树。我们从第二个位置向上调整,直到最后一个位置的数为止。
void hpSort(int* a, int n)
{assert(a);//从第二个数开始向上调整for (int i = 1; i < n; i++){adjustUp(a, i);}
}
(2)堆的向下调整算法
现在我们给出一个数组,逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提:左右子树必须是一个堆,才能调整。
有人可能认为向下调整算法的时间复杂度为o(n*log2n),其实并不是,时间复杂度其实为o(n),由于在倒数第二层时,每个元素只调整了一次,倒数第三层调整了两次,也可以通过数学公式来证明,通过错位相减法,最终得到了向下调整算法的时间复杂度为o(n)。
void hpSort(int* a, int n)
{assert(a);//从非叶子结点开始向下调整for (int i = (n-1)-1/2; i >= 0; i--){adjustDown(a, n, i);}
}
从非叶子结点开始调整,可以从最后一个结点的父节点处开始,进行向下调整,直至调整到根节点。
2. 利用堆删除思想来进行排序
(1)当我们要对数据进行降序排列时,我们先建立一个小堆,即父节点的数据小于子节点的数据。
(2)将最后一个结点与第一个结点互换,此时得到的最后一个结点的数据就是最小的数。
(3)此时对第一个结点向下调整,使其恢复成为一个小堆,此时堆顶元素就是整个堆中次小的数。
(4)此时,我们把最后一个结点与原来结点分离,只是看作分离,只是将其余结点从新进行之前的操作,直至堆的大小为1。
void hpSort(int* a, int n)
{assert(a);//从第二个数开始向上调整/*for (int i = 1; i < n; i++){adjustUp(a, i);}*///从非叶子结点开始向下调整for (int i = (n-1)-1/2; i >= 0; i--){adjustDown(a, n, i);}for(int end=n - 1 ; end > 0 ; end--){swap(&a[0], &a[end]);adjustDown(a, end ,0);}
}
3.堆排序的时间复杂度
我们知道了向下调整算法来建堆的时间复杂度为o(n),所以我们选择向下调整算法来建堆,在建完堆之后,我们就进行交换并且向下调整,排序的时间复杂度为o(n*log2n),所以总和的时间复杂度为o(n*log2n)。
4.源码
hpsort.c
void hpSort(int* a, int n)
{assert(a);//从第二个数开始向上调整/*for (int i = 1; i < n; i++){adjustUp(a, i);}*///从非叶子结点开始向下调整for (int i = (n-1)-1/2; i >= 0; i--){adjustDown(a, n, i);}for(int end=n - 1 ; end > 0 ; end--){swap(&a[0], &a[end]);adjustDown(a, end ,0);}
}
test.c
void test1()
{//TestTopk();int a[] = { 70, 56, 30, 25, 15, 10, 75, 33, 50, 69 };for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i){printf("%d ", a[i]);}printf("\n");hpSort(a, sizeof(a) / sizeof(a[0]));for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i){printf("%d ", a[i]);}printf("\n");}
总结
今天我们学习了堆排序的概念,实现,以及时间复杂度,过两天我会继续发布关于各种排序的文章,希望大家支持。
相关文章:

【数据结构初阶】堆排序
目录 前言 概念 堆排序的实现 1.建堆 (1)堆向上调整算法 (2)堆的向下调整算法 2. 利用堆删除思想来进行排序 3.堆排序的时间复杂度 4.源码 总结 前言 前边我们学习了堆的实现,对堆的每个接口都进行了详细的讲…...

Day5: platformDriver-1
Platform Driver (1) Linux kernel中大部分设备可以归结为平台设备,因此大部分的驱动是平台驱动(patform driver) 什么是平台设备 平台设备是linux的设备模型中一类设备的抽象。 内核中的描述: Platform devices are devices t…...

开发手册——一、编程规约_7.控制语句
这篇文章主要梳理了在java的实际开发过程中的编程规范问题。本篇文章主要借鉴于《阿里巴巴java开发手册终极版》 下面我们一起来看一下吧。 1. 【强制】在一个 switch 块内,每个 case 要么通过 break / return 等来终止,要么注释说明程序将继续执行到哪…...

python每日学9 : windows上配置gitee的远程仓库,git的初步使用
在开发中,如果遇到复杂的项目,使用版本控制是非常有必要的,如果涉及到多端开发,那么还需要使用远程仓库。本文作个简单记录,记录下git初步使用。 1 下载与安装 git还有几个ui版本,但是开始使用的话&#…...

精确率与召回率,ROC曲线与PR曲线
精确率与召回率,ROC曲线与PR曲线 在机器学习的算法评估中,尤其是分类算法评估中,我们经常听到精确率(precision)与召回率(recall),ROC曲线与PR曲线这些概念,那这些概念到底有什么用处呢? 首先,…...

现代操作系统——Linux架构与学习
小白的疑惑 在我决定从事嵌入式(应用层)方面的工作时,我查询了大量资料该如何学习,几乎所有观点不约而同的都指向了学习好Linux,大部分工作都是在Linux环境下来进行工作的。于是我雄心勃勃的去下载Linux,可…...
中文代码82
PK 嘚釦 docProps/PK 嘚釦羸 r docProps/app.xml潙蚽?勶曻Q顗濔S? 錞礖剅D柍珘m?鳞?ぷ辷f硌?2?upc厭Y樐8 rU y搪m眾&a?珪?紓 玺鶋瑣襚? ?i嘲rN?布倖儇?攊橌??嚗猝)芻矂2吟腊K湞?CK臶>鸘\?ΔF滋齢q旮T?桀?;偉 A軥v蕯朾偤佷3?е…...

顺序表(一篇带你掌握顺序表)
目录 一、顺序表是什么 1.1 概念 1.2 分类 1.3 结构 二、顺序表的基本操作 2.1 前绪准备 2.2 初始化 2.3 扩容 2.5 尾插 2.6 打印 2.7 尾删 2.8 头插 2.9 头删 2.10 在pos位置插入 2.11 删除pos位置的数据 2.12 查找 三、完整代码 3.1 Test.c文件 3.2 SeqList.h…...

【SpringCloud】SpringCloud教程之Feign实战
目录前言SpringCloud Feign远程服务调用一.需求二.两个服务的yml配置和访问路径三.使用RestTemplate远程调用(order服务内编写)四.构建Feign(order服务内配置)五.自定义Feign配置(order服务内配置)六.Feign配置日志(oder服务内配置)七.Feign调优(order服务内配置)八.抽离Feign前…...

嵌入式linux必备内存泄露检测神器
Valgrind介绍 Valgrind是一个可移植的动态二进制分析工具集,主要用于发现程序中的内存泄漏、不合法内存访问、使用未初始化的内存、不正确的内存释放以及性能问题等,可在Linux和Mac OS X等平台上使用。 Valgrind由多个工具组成,其中最常用的…...

设计模式之行为型模式
四、行为型模式 行为型模式用于描述程序在运行时复杂的流程控制,即描述多个类或对象之间怎样相互协作共同完成单个对象都无法单独完成的任务,它涉及算法与对象间职责的分配。 行为型模式分为类行为模式和对象行为模式,前者采用继承机制来在…...
解密 三岁的三岁到底为什么叫做三岁?
机缘 那一年,一次奇奇怪怪的挫折与一次奇奇怪怪的成长。 在学习Python的路上总觉得少了点什么,是心情?是机遇?还是力量? 都不是又都是! 缺少一个实践和记忆的平台 记性不好是硬伤 前一天学的下一秒就忘记了…...
id选择器
id选择器可以为特定的id的标签进行css美化 使用方法: 标签内设好 id值, CSS的id选择器以“#id名”来调用 注意 所有标签都有id值id属性值类似于身份证号码,在一个页面中是唯一的值,不可重复一个标签上只能有一个id属性值一个id属性…...
《科技之巅3》读书笔记
文章目录书籍信息人工智能,“吃一堑长一智”的机器人机交互,为解决“交流障碍”问题而生硬件与算法,好马还需好鞍模式创新,赋予技术新的定义云与数据共享,灵活应对信息的爆发式增长“机器人”,从电影和小说…...

18.用于大型程序的工具
文章目录用于大型程序的工具18.1异常处理18.1.1抛出异常栈展开栈展开过程中对象被自动销毁析构函数与异常异常对象18.1.2捕获异常查找匹配的处理代码重新抛出捕获所有异常的处理代码18.1.3函数try语句块与构造函数18.1.4noexcept异常说明违反异常说明异常说明的实参noexcept运算…...

mysql一主键uuid和自增的选择
文章目录 1.自增ID的优缺点1.1 优点1.2 缺点1.3 不适合以自增ID主键作为主键的情况2.UUID作为主键2.1 介绍2.2 优点2.3 缺点3.有序UUID作为主键3.1 介绍3.2 演示使用3.2.1 前提知识3.2.1.1 数据类型 - binary3.2.1.2 函数 - hex()3.2.1.3 函数 - unhex()3.2.2 数据库层3.2.3 JA…...

【EDA工具使用】——VCS和Verdi的联合仿真的简单使用
目录 1.芯片开发所需的工具环境 2.编译仿真工具 3.三步式混合编译仿真(最常用)编辑 4.两步式混合编译仿真编辑 5.VCS的使用 6.verdi的使用 1.产生fsdb文件的两种方法编辑 1.芯片开发所需的工具环境 2.编译仿真工具 3.三步式混合编译仿真…...

【Java学习笔记】4.Java 对象和类
前言 本章介绍Java的对象和类。 Java 对象和类 Java作为一种面向对象语言。支持以下基本概念: 多态继承封装抽象类对象实例方法重载 本节我们重点研究对象和类的概念。 对象:对象是类的一个实例(对象不是找个女朋友)&#x…...

39. 实战:基于api接口实现视频解析播放(32接口,窗口化操作,可导出exe,附源码)
目录 前言 目的 思路 代码实现 需要导入的模块 1. 导入解析网站列表,实现解析过程 2. 设计UI界面 3. 设置窗口居中和循环执行 4. 注意事项 完整源码 运行效果 总结 前言 本节将类似34. 实战:基于某api实现歌曲检索与下载(附完整…...

基于灵动 MM32 微控制器的便携式血氧仪方案
基于灵动 MM32 微控制器的便携式血氧仪: - Cortex-M0() 最高主频 72MHz 可实现血氧饱和度信号采集、算法操作和 LED 显示操作 - 高性能的 1Msps 12b ADC 能对光电采样结果进行大数据量的暂存和处理,提高采样的效率并有助于对结果做高精度的计算 - 100…...

VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...

ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...

蓝桥杯3498 01串的熵
问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798, 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的
修改bug思路: 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑:async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...