【数据结构--八大排序】之堆排序
💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤
📃个人主页 :阿然成长日记 👈点击可跳转
📆 个人专栏: 🔹数据结构与算法🔹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…...
线性代数(七) 矩阵分析
前言 从性线变换我们得出,矩阵和函数是密不可分的。如何用函数的思维来分析矩阵。 矩阵的序列 通过这个定义我们就定义了矩阵序列的收敛性。 研究矩阵序列收敛性的常用方法,是用《常见向量范数和矩阵范数》来研究矩阵序列的极限。 长度是范数的一个特…...
myArm 全新七轴桌面型机械臂
引言 在不断演进的科技世界中,我们始终追求创新和卓越,以满足客户的需求并超越他们的期望。今天,我们很高兴地宣布我们的最新产品——myArm 300 Pi,一款七轴的桌面型机械臂。这款产品的独特之处在于其灵活性和可编程性,…...
tomcat乱码解决
解决乱码 1、修改bin\catalina.bat配置文件 修改tomcat的配置文件,找到tomcat路径下的\bin目录下的catalina.bat文件,修改 set “JAVA_OPTS%JAVA_OPTS% %JSSE_OPTS% -Dfile.encodingUTF-8 -Dsun.jnu.encodingUTF-8 ” 2、修改conf\logging.properties配置…...
【Linux】详解线程第三篇——线程同步和生产消费者模型
线程同步和生消模型 前言正式开始再次用黄牛抢票来讲解线程同步的思想通过条件变量来实现线程同步条件变量接口介绍初始化和销毁pthread_cond_waitsignal和broadcast 生产消费者模型三种关系用基本工程师思维再次理解基于生产消费者模型的阻塞队列版本一版本二多生多消 利用RAI…...
k8s 安装
文章目录 k8s 客户端安装k8s集群minikubekindkubeadm 验证 k8s 客户端 用于连接k8s集群,建议下载1.23.x的版本,其他的版本本地运行可能会有莫名其妙的报错 https://dl.k8s.io/release/v1.23.16/bin/linux/amd64/kubectl 安装k8s集群 minikube Minik…...
红队打靶:THE PLANETS: MERCURY打靶思路详解(vulnhub)
目录 写在开头 第一步:主机发现和端口扫描 第二步:Web渗透 第三步:获取初步立足点并搜集信息 第四步:软连接劫持sudo提权 总结与思考 写在开头 本篇博客在自己的理解之上根据大佬红队笔记的视频进行打靶,详述了…...
【网络协议】IP
当连接多个异构的局域网形成强烈需求时,用户不满足于仅在一个局域网内进行通信,他们希望通过更高一层协议最终实现异构网络之间的连接。既然需要通过更高一层的协议将多个局域网进行互联,那么这个协议就必须为不同的局域网环境定义统一的寻址…...
Python 布尔类型
布尔值表示两个值之一:True(真)或False(假)。 布尔值 在编程中,您经常需要知道一个表达式是否为True或False。 您可以在Python中评估任何表达式,并获得两个答案之一:True或False。…...
iOS设备管理器iMazing比iTunes好用吗?有哪些优势
虽然 iTunes 是 Apple 官方指定的 iPhone 数据备份和管理工具,但是一直以来 iTunes 卡顿的使用体验和过慢的备份过程为不少人诟病。如果大家也被 iTunes 体验不佳的备份和管理功能所困扰,那么简单易用、功能强大的iMazing 能为你解决这个问题。 iMazing…...
Opengl之深度测试
在坐标系统小节中,我们渲染了一个3D箱子,并且运用了深度缓冲(Depth Buffer)来防止被阻挡的面渲染到其它面的前面。在这一节中,我们将会更加深入地讨论这些储存在深度缓冲(或z缓冲(z-buffer))中的深度值(Depth Value),以及它们是如何确定一个片段是处于其它片段后方的。 …...
网站建设规划大纲/提高工作效率的重要性
目前来说,win8没有本地数据库。使用sqlite作为win8的数据存取是一种比较实在的解决方案。 我在使用sqlite过程中,遇到过一些问题,现在做一个小结作为本次的开发笔记吧。 (1) sqlite在vs2012上的安装教程参考:sqlite for win8. sq…...
企业网站建设品牌/网站公司
简单的jQuery代码段通过禁用与按钮关联的onclick事件来停止单击时清除输入。 这只是失败的代码,很抱歉,没有适当的示例。 $(.del).click(function(){onclick $(this).attr(onclick);$(this).attr(onclick,);showConfirm(onclick);return false; });…...
vue适合什么网站开发/自媒体平台注册下载
工作流(Workflow),就是“业务过程的部分或整体在计算机应用环境下的自动化”,它主要解决的是“使在多个参与者之间按照某种预定义的规则传递文档、信息或任务的过程自动进行,从而实现某个预期的业务目标,或者促使此目标的实现”。…...
佛山做网站/网络推广外包搜索手机蛙软件
php 获取当前时间戳、日期并精确到毫秒首先,我们封装一个获取时间戳的方法:第一种方法:时间戳13位/*** 获取时间戳到毫秒* return bool|string*/public static function getMillisecond(){list($msec, $sec) explode( , microtime());$msect…...
国际交易所app下载/抖音搜索优化
回文字符串 时间限制:3000 ms | 内存限制:65535 KB 难度:4描述 所谓回文字符串,就是一个字符串,从左到右读和从右到左读是完全一样的,比如"aba"。当然,我们给你的问题不会再简单到判…...
pc端网站建设相关查阅资料/今天国内新闻10条
首先,我们先普及一下编程语言的基础知识。其实无论用任何编程语言来开发程序,都是为了让计算机干活,比如编写一篇文章,下载一首MP3等,而计算机干活的CPU只认识机器的指令,所以,尽管不同的编程语…...