【数据结构--八大排序】之堆排序
💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤
📃个人主页 :阿然成长日记 👈点击可跳转
📆 个人专栏: 🔹数据结构与算法🔹C语言进阶
🚩 不能则学,不知则问,耻于问人,决无长进
🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍
文章目录
- 堆排序
- 一、🌱排降序
- 1.思路:
- 2.代码实现:
- 3.测试结果
- 4.总代码
- 二、🌸排升序
- 1.思路:
- 2.代码实现:
- 3.测试结果:
- 4.总代码
- 三、堆排序的时间复杂度
堆排序
一、🌱排降序
口诀:排降序,建小堆
1.思路:
(1)首先使用从下到上的方法建立小堆;如下图
(2)堆顶与最后一个节点交换,由于是小堆,堆顶是最小值。交换后,就选出了最小值
并将其放到数组的组后位置,
(3).将堆的长度减1【end–】(数组长度减1)。
(4).在对剩下的堆进行基于小堆的向下调整,从而将第二小的数调整到了堆顶。
重复步骤2.3.4,end一直减到0;
4.最后,这个原本存储小堆的数组,就变成了一个从小到大的降序数组。
2.代码实现:
1.交换
//交换
void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}
2.修改AdjustDown(a, end, 0);为调小堆
基于小堆的向下调整
```cvoid AdjustDownxiao(int* a, int n, int parent)
{int child = parent * 2 + 1;//一直交换到数的最后,也就是数组的最后一个位置while (child < n){if (child + 1 < n && a[child + 1] < a[child]){child++;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);// 继续往下调整parent = child;child = parent * 2 + 1;}else{return;}}
}
3.排降序
void HeapSortDES(int* a, int n)
{//建立小堆for (int i = (n-1-1)/2; i >= 0; i--){AdjustDownxiao(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);//每次调整从根0到end,end每次会减1。AdjustDownxiao(a, end, 0);--end;}
}
3.测试结果
4.总代码
//交换
void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}
//基于小堆的向下调整
void AdjustDownxiao(int* a, int n, int parent)
{int child = parent * 2 + 1;//一直交换到数的最后,也就是数组的最后一个位置while (child < n){if (child + 1 < n && a[child + 1] < a[child]){child++;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);// 继续往下调整parent = child;child = parent * 2 + 1;}else{return;}}
}//降序
void HeapSortDES(int* a, int n)
{//建立小堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDownxiao(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);//每次调整从根0到end,end每次会减1。AdjustDownxiao(a, end, 0);end--;}
}
二、🌸排升序
口诀:排升序,建大堆
意思是:想要将数组的顺序变成一个升序的,那么可以建立一个大堆存在数组中,在对堆进行调整。即可将数组变成一个升序数组。
1.思路:
首先使用从下到上的方法建立大堆;
1.堆顶与最后一个节点交换,由于是大堆,堆顶是最大值。交换后,就选出了最大值并将其放到数组的组后位置,
2.并将堆的长度减1(数组长度减1)。
3.在对剩下的堆进行基于大堆的向下调整,从而将第二大的数调整到了堆顶。
4.最后,这个原本存储大堆的数组,就变成了一个从小到大的升序数组。
2.代码实现:
1.交换
//交换
void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}
2.基于大堆的向下调整
//基于大堆的向下调整
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;//一直交换到数的最后,也就是数组的最后一个位置while (child < n){if (child + 1 < n && a[child + 1] > a[child]){child++;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);// 继续往下调整parent = child;child = parent * 2 + 1;}else{return;}}
}
3.排升序
//排升序
void HeapSortASC(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]);//每次调整从根0到end,end每次会减1。AdjustDown(a, end, 0);end--;}
}
3.测试结果:
4.总代码
//交换
void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;//一直交换到数的最后,也就是数组的最后一个位置while (child < n){if (child + 1 < n && a[child + 1] > a[child]){child++;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);// 继续往下调整parent = child;child = parent * 2 + 1;}else{return;}}
}//升序
void HeapSortASC(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]);//每次调整从根0到end,end每次会减1。AdjustDown(a, end, 0);end--;}
}
三、堆排序的时间复杂度
堆排序分两步:1.建堆(使用时间复杂度更低的向下调整建堆)2.排序
向下调整建堆的时间复杂度为O(n);
n-1次删除操作的时间复杂度为O(nlogn);
所以总操作时间复杂度为O(nlogn)
相关文章:

【数据结构--八大排序】之堆排序
💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃个人主页 :阿然成长日记 …...

c# 中的类
反射 Activator.CreateInstance class Program {static void Main(string[] args){//反射Type t typeof(Student);object o Activator.CreateInstance(t, 1, "FJ");Student stu o as Student;Console.WriteLine(stu.Name);//动态编程dynamic stu2 Activator.Cre…...

基于单片机的煤气泄漏检测报警装置设计
一、项目介绍 煤气泄漏是一种常见的危险情况,可能导致火灾、爆炸和人员伤亡。为了及时发现煤气泄漏并采取相应的安全措施,设计了一种基于单片机的煤气泄漏检测报警装置。 主控芯片采用STM32F103C8T6作为主控芯片,具有强大的计算和控制能力。…...
[导弹打飞机H5动画制作] 导弹每次飞行的随机路线制作
技术核心提示: 第一步:检测引导层插件是否具备,如果没有手工添加: createjs.MotionGuidePlugin.install(); 第二步:增加全局变量: var fValue=0; var iOddEven =0; var missileObj=null; 第三步:填写 第一帧 代码: if (missileObj)stage.removeChild(missileObj);missile…...

OpenCV实现FAST算法角点检测 、ORB算法特征点检测
目录 1 Fast算法 1.1 Fast算法原理 1.2 实现办法 1.2.1 机器学习的角点检测器 1.2.2 非极大值抑制 1.3 代码实现 1.4 结果展示 2 ,ORB算法 2.1代码实现 2.2 结果展示 1 Fast算法 1.1 Fast算法原理 1.2 实现办法 1.2.1 机器学习的角点检测器 1.2.2 …...

【Unity的 Built-in 渲染管线下实现好用的GUI模糊效果_Blur_案例分享(内附源码)】
CGPROGRAM实现好用的GUI模糊效果 实现Blur模糊方式1C#代码如下方式1_Shader代码如下实现Blur模糊方式2方式2_Shader如下实现Blur模糊方式1 其他的模糊效果,在这一篇。 效果如图: 新建一个C#文件,命名为"CommandBlur",打开C#,删除内容,复制粘贴下面的代码:…...

AR智能眼镜:提升现场服务技能、效率与盈利能力的利器(一)
随着技术的不断进步,现场服务组织正朝着远程支持转变,用以解决技能差距和生产力问题,提高员工培训和操作效率,同时为企业提高利润率,创造竞争优势。 本文将探讨增强现实(AR)、辅助现实…...

ChatGPT 在机器学习中的应用
办公室里一个机器人坐在人类旁边,Artstation 上的流行趋势,美丽的色彩,4k,充满活力,蓝色和黄色, DreamStudio出品 一、介绍 大家都知道ChatGPT。它在解释机器学习和深度学习概念方面也非常高效,…...

【JavaEE】锁策略
文章目录 前言1. 乐观锁和悲观锁2. 重量级锁和轻量级锁3. 自旋锁和挂起等待锁4. 公平锁和非公平锁5. 可重入锁和非可重入锁6. 读写锁Java synchronized 分别对应哪些锁策略1. 乐观锁和悲观锁2. 重量级锁和轻量级锁3. 自旋锁和挂起等待锁4. 公平锁和非公平锁5. 可重入锁和非可重…...

在 SDXL 上用 T2I-Adapter 实现高效可控的文生图
T2I-Adapter 是一种高效的即插即用模型,其能对冻结的预训练大型文生图模型提供额外引导。T2I-Adapter 将 T2I 模型中的内部知识与外部控制信号结合起来。我们可以根据不同的情况训练各种适配器,实现丰富的控制和编辑效果。 同期的 ControlNet 也有类似的…...

Python分支结构和循环结构
嗨喽~大家好呀,这里是魔王呐 ❤ ~! python更多源码/资料/解答/教程等 点击此处跳转文末名片免费获取 一.分支结构 分支结构是根据判断条件结果而选择不同向前路径的运行方式,分支结构分为:单分支,二分支和多分支。 1࿰…...
Unity调用API函数对系统桌面和窗口截图
Unity3D调用WINAPI函数对系统窗口截图 引入WINAPI函数调用WINAPI函数进行截图使用例子 引入WINAPI函数 using System; using System.Collections; using System.Runtime.InteropServices; using System.Drawing;[DllImport("user32.dll")]private static extern Int…...
【问题思考总结】CPU怎么访问磁盘?CPU只有32位,最多只能访问4GB的空间吗?
问题 在学习操作系统的时候发现了这样一个问题,32位的CPU寻址空间只有4GB,难道只有4GB的空间可以使用吗?以此为始,我开始了一些思考。 思考 Q1:首先,我似乎混淆了一个概念,内存和外存&#x…...
UG NX二次开发(C++)-CAM-根据刀具对程序组进行重新分组
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 1、前言2、在UG NX中创建一个三维模型3、在UG NX/CAM中创建多个加工程序4、采用UG NX二次开发(NXOpen)实现按照刀具分组程序组4.2 创建UI Styler4.1 实现逻辑4.2 生成的代码如下:4.3 测试效果4.…...

Unity如何实现TreeView
前言 最近有一个需求,需要实现一个TreeView的试图显示,开始我一直觉得这么通用的结构,肯定有现成的UI组件或者插件可以使用,结果,找了好久,都没有找到合适的插件,有两个效果差强人意。 最后在回家的路上突然灵光一闪,想到了一种简单的实现方式,什么插件都不用,仅使用…...

Android widget 小部件使用指南强化版
Android widget 小部件使用指南强化版 一、简单UI的小部件二、含集合的小部件三、可配置的小部件四、可控制的小部件五、Android 12 Widget 更新 小部件是主屏幕定制的一个重要方面。您可以将它们视为应用程序最重要的数据和功能的“概览”视图,这些数据和功能可以直…...

Linux下C语言操作网卡的几个代码实例?特别实用
前面写了一篇关于网络相关的文章:如何获取当前可用网口。 《简简单单教你如何用C语言列举当前所有网口!》 那么如何使用C语言直接操作网口? 比如读写IP地址、读写MAC地址等。 一、原理 主要通过系统用socket()、ioctl()、实现 int sock…...
noip2011选择旅馆
1.审题:第一个人与第二个人入住的旅馆要求是同色的; 两个人去消费的旅馆并没有要求与入住的旅馆是同色的(这点要小心) 2.要求记录以下数据: 1)a[color]表示当前同为颜色color的旅馆数 2)b[co…...

vue造轮子完整指南--npm组件包开发步骤
一、项目包文件的创建和初始化。 1. 新建项目包。 vue create <Project Name> //用于发布npm包的项目文件名 ps:一般选择自定义,然后不需要Vuex和Router,其他选项按自己实际情况选择安装即可。 2.修改原始src文件名、新增组件项目存放文件和修改…...

28 drf-Vue个人向总结-1
文章目录 前后端分离开发展示项目项补充知识开发问题浏览器解决跨域问题 drf 小tips设置资源root目录使用自定义的user表设置资源路径media数据库补充删除表中数据单页面与多页面模式过滤多层自关联后端提交的数据到底是什么jwt token登录设置普通的 token 原理使用流程解析 jw…...

label-studio的使用教程(导入本地路径)
文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...
MySQL账号权限管理指南:安全创建账户与精细授权技巧
在MySQL数据库管理中,合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号? 最小权限原则…...

2025季度云服务器排行榜
在全球云服务器市场,各厂商的排名和地位并非一成不变,而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势,对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析: 一、全球“三巨头”…...

佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...
深入浅出Diffusion模型:从原理到实践的全方位教程
I. 引言:生成式AI的黎明 – Diffusion模型是什么? 近年来,生成式人工智能(Generative AI)领域取得了爆炸性的进展,模型能够根据简单的文本提示创作出逼真的图像、连贯的文本,乃至更多令人惊叹的…...

【堆垛策略】设计方法
堆垛策略的设计是积木堆叠系统的核心,直接影响堆叠的稳定性、效率和容错能力。以下是分层次的堆垛策略设计方法,涵盖基础规则、优化算法和容错机制: 1. 基础堆垛规则 (1) 物理稳定性优先 重心原则: 大尺寸/重量积木在下…...

消息队列系统设计与实践全解析
文章目录 🚀 消息队列系统设计与实践全解析🔍 一、消息队列选型1.1 业务场景匹配矩阵1.2 吞吐量/延迟/可靠性权衡💡 权衡决策框架 1.3 运维复杂度评估🔧 运维成本降低策略 🏗️ 二、典型架构设计2.1 分布式事务最终一致…...

恶补电源:1.电桥
一、元器件的选择 搜索并选择电桥,再multisim中选择FWB,就有各种型号的电桥: 电桥是用来干嘛的呢? 它是一个由四个二极管搭成的“桥梁”形状的电路,用来把交流电(AC)变成直流电(DC)。…...