【数据结构】第十八弹---C语言实现堆排序
✨个人主页: 熬夜学编程的小林
💗系列专栏: 【C语言详解】 【数据结构详解】【C++详解】
目录
1、堆排序
1.1、基本思想
1.2、初步代码实现
1.3、代码优化
1.4、代码测试
总结
1、堆排序
在博主数据结构第十二弹---堆的应用有详细讲解堆排序喔~~~
数据结构第十二弹---堆的应用https://blog.csdn.net/2201_75584283/article/details/135348207https://blog.csdn.net/2201_75584283/article/details/135348207
1.1、基本思想
堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆,排降序建小堆。
为什么升序用到的是大堆呢?
因为:大堆的堆顶是最大的数,可以将其放在数组尾,然后再通过向下调整算法找到次大的数。而小堆的堆顶是最小的数,需要放在第一个位置,如果用原来的堆找不到次小的数,而重新建堆则会更加繁琐。
降序用小堆同理。
动图如下:
1.2、初步代码实现
堆排序的实现可以分为两部分:构建最大堆(或最小堆)和执行排序过程。
注意:此处我们实现的是大堆!!!
第一步:建堆
我们此处是对数组内部的数进行排序,那么怎样才能创建成大堆呢?
这里我们可以使用向上调整算法,从第二个数开始遍历数组,如果不满足大堆则交换父子元素。
for (int i = 1; i < n; i++)
{AjustUp(a, i);
}
大堆向上调整:
- 将被调整的数值与其父节点比较,若是大于父节点,则与父节点交换。
- 若子节点下标为child,父节点下标为(child - 1) / 2。
- 当子节点小于父节点时,或者当子节点已经为堆顶时,停止比较。
代码实现:
void AdjustUp(int* a, int child)
{int parent = 0;while (child > 0){parent = (child - 1) / 2;if (a[child] > a[parent]){Swap(&a[child], &a[parent]);child = parent;}else{break;}}
}
小堆向上调整:
与向下调整大堆思想的唯一区别就是:将被调整的数值与父节点比较,若是小于父节点,则与父节点交换,将小根堆比较条件改为小于即可
if (a[child] < a[parent])//孩子小于父亲则交换
{...
}
每次向上调整算法的时间复杂度为O(log N)。
所以使用向上调整建好堆的时间复杂度为(N*log N)
第二步:执行排序操作
进行了向上调整之后,此时的数组就是一个大堆了,要怎样才能达到升序呢?
- 使用大根堆选出最大的数,放在数组的最后一个位置,依次选出进行排序。
- 将堆顶和最后一个数交换。
- 然后将新堆顶向下调整,形成堆。
- 向下调整时,注意交换后的最后位置不在新堆里,所以要下标要减一。
- 没有对堆结构造成破坏,不用对每个数都调整。
//2.向下调整 O(N*logN)
int end = n - 1;
while (end > 0) //从最后一个位置开始交换并调整
{Swap(&arr[0], &arr[end]);AdjustDown(arr, end, 0);//此处为大根堆向下调整方式end--;
}
大堆向下调整:
- 将被调整的数值与其最大的子节点比较,若是小于最大的子节点,则与该子节点交换。
- 若父节点下标为parent,左子节点下标为 parent * 2 + 1,右子节点的下标为 parent * 2 + 2。
- 获取最大的子节点时,可以先将左子节点作为最大节点,再与右子节点比较,若是大于右子节点,则将左子节点下标加1得到右子节点下标。
- 再循环体内比较左右子节点之前,要先判断右子节点存在,防止堆最后一个节点是左子节点造成越界访问。
- 当子节点小于父节点时,或者当子节点超过堆的范围时,停止比较。
//向下调整算法 大堆
void AdjustDown(int* a, int size, int parent)
{//1.假设左孩子为小的数据int child = parent * 2 + 1;while (child < size){//2.如果左孩子>右孩子 则将右孩子赋值//有可能只有左孩子 所以加条件//以下未有左右孩子且左孩子>右孩子情况,则将child++if (child + 1 < size && a[child] < a[child + 1]){child++;}//3.将孩子与父亲进行比较 如果孩子小则交换//然后将父亲和孩子移动到下一个位置if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
小堆向下调整:
- 将被调整的数值与其最小的子节点比较,若是大于最小的子节点,则与该子节点交换。
- 将小根堆向下调整时左右子节点的比较条件和父节点与子节点的比较改为小于即可。
if (child + 1 < size && a[child] > a[child + 1])
{...
}if (a[child] < a[parent])
{...
}
堆排序的代码如下:
void HeapSort(int arr[], int n)
{assert(arr);//1.建堆 向上调整 O(N*logN)for (int i = 1; i < size; i++){AdjustUp(arr, i);}//2.向下调整 O(N*logN)int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDown(arr, end, 0);end--;}
}
1.3、代码优化
在建堆的时候,我们既可以使用向上调整算法建堆,也可以使用向下调整算法建堆,在堆的应用那一弹我们计算了向下调整算法建堆的时间复杂度,对整个数组进行向下调整的时间复杂度是O(N),因此我们在堆排序的时候也可以统一使用向下调整算法!!!
向下调整:
- 向下调整是从后往前调整,先将后面构成堆,再调整上面的节点。
- 以叶子节点作为根进行向下调整是完全没有必要的,叶子节点没有子节点,所以对最后一个叶子节点的父节点开始向下调整。
- 最后一个节点下标是n-1,它的父节点为 (n-1-1) / 2。
//1.向下调整建堆 O(N)
for (int i = (n - 1 - 1) / 2; i >= 0; i--)//从n-2 到 0 进行调整
{AdjustDown(arr, n, i);
}
堆排序代码如下:
void HeapSort(int arr[], int n)
{assert(arr);//1.向下调整建堆 O(N)for (int i = (n - 1 - 1) / 2; i >= 0; i--)//从n-2 到 0 进行调整{AdjustDown(arr, n, i);}//2.向下调整 O(N*logN)int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDown(arr, end, 0);end--;}
}
1.4、代码测试
测试代码:
//测试堆排序
int main()
{int a[] = { 9,8,7,6,5,4,3,2,1,0 };//给一组数据int sz = sizeof(a) / sizeof(a[0]);//计算数组元素个数printf("排序前:\n");ArrayPrint(a, sz);HeapSort(a, sz);printf("排序后:\n");ArrayPrint(a, sz);return 0;
}
测试结果:
堆排序的特性总结:
1. 堆排序使用堆来选数,效率就高了很多。
2. 时间复杂度:O(N*logN)。
3. 空间复杂度:O(1)。
4. 稳定性:不稳定。5. 复杂性:复杂。
总结
本篇博客就结束啦,谢谢大家的观看,如果公主少年们有好的建议可以留言喔,谢谢大家啦!
相关文章:

【数据结构】第十八弹---C语言实现堆排序
✨个人主页: 熬夜学编程的小林 💗系列专栏: 【C语言详解】 【数据结构详解】【C详解】 目录 1、堆排序 1.1、基本思想 1.2、初步代码实现 1.3、代码优化 1.4、代码测试 总结 1、堆排序 在博主数据结构第十二弹---堆的应用有详细讲解堆…...

[面试题]Kafka
[面试题]Java【基础】[面试题]Java【虚拟机】[面试题]Java【并发】[面试题]Java【集合】[面试题]MySQL[面试题]Maven[面试题]Spring Boot[面试题]Spring Cloud[面试题]Spring MVC[面试题]Spring[面试题]MyBatis[面试题]Nginx[面试题]缓存[面试题]Redis[面试题]消息队列[面试题]…...

centos7 离线安装zip和unzip
解压的时候发现不能解压,报-bash: unzip: command not found 1、访问https://www.rpmfind.net/linux/rpm2html/search.php?queryzip&submitSearch…&systemcentos&arch#/ 2、输入zip和centos搜索,选择el7下载 3、输入unzip和centos搜索&am…...
Linux下lsof命令使用
目录 lsof 命令使用指南基本语法常用选项使用示例 lsof vs netstatlsofnetstat区别示例对比 lsof 命令使用指南 lsof (List Open Files) 是一个用于列出当前系统中打开文件的命令,适用于 Unix 和类 Unix 操作系统。它不仅可以列出常规文件,还可以列出打…...

基于ChatGPT的大型语言模型试用心得
近年来,ChatGPT这样的大型语言模型,它如同一颗冉冉升起的新星,迅速在商业、教育、娱乐等多个领域照亮了创新的天空,极大地革新了我们的工作与日常生活。 最近我发现一些国内用户也能自由访问的中文ChatGPT APP。这个平台不仅提供…...
Python 列表添加多个值(四种方法)
Python 列表添加多个值有多种方法,以下是其中几种实现方法: 一、使用extend()方法 Python 中列表对象有一个 extend() 方法,它可以一次性添加另一个列表中的所有元素到当前列表中。 例1: a = [1, 2, 3] b = [4, 5, 6] a.extend(b)...

VMware RedHat虚拟机磁盘扩容(添加磁盘和扩展磁盘)
前言 自己的电脑上配一个虚拟机还是很有必要的,用起来比双系统方便一点,之前搞了100g的ubuntu没用到,后面重装redhat觉得随便搞个20g就够用了,后面用到之后就遇到磁盘不够用的情况,只能说情况允许的话,磁盘…...
最近,GPT-4o横空出世。对GPT-4o这一人工智能技术进行评价,包括版本间的对比分析、GPT-4o的技术能力以及个人整体感受等
GPT-4o是一款引人瞩目的人工智能技术,它在之前版本的基础上取得了长足的进步。本文将对GPT-4o进行评价,包括版本间的对比分析、GPT-4o的技术能力以及个人整体感受等。 首先,我们来进行GPT-4o与之前版本的对比分析。GPT-4o相较于GPT-3和GPT-2…...
C#面:C#支持多重继承么?
C#不支持多重继承。在C#中,一个类只能直接继承自一个基类。这是由于C#的设计目标之一是避免多重继承可能带来的复杂性和潜在的问题。 然而,C#提供了接口(interface)的概念来实现类似多重继承的功能。一个类可以实现多个接口&…...

细说MCU修改回调函数调用模式的方法
目录 1、硬件及工程 2、实现方法 (1)修改while(1)中的代码: (2)修改2 (3)修改3 (4)修改4 (5)修改5 3、下载并运行 在本文作者的文章中&a…...

Java共享台球室无人系统支持微信小程序+微信公众号
共享台球室无人系统 🎱 创新台球体验 近年来,共享经济如火如荼,从共享单车到共享汽车,无一不改变着我们的生活方式。而如今,这一模式已经渗透到了更多领域,共享台球室便是其中之一。不同于传统的台球室&a…...

如何开发一个海外仓系统?难度在哪,怎么选择高性价解决方案
作为海外仓管理的重要工具,海外仓系统的实际应用价值还是非常高的。为了让大家能更好的理解wms海外仓系统,今天会介绍海外仓系统开发的逻辑架构,以及作为海外仓企业要怎么确定高性价比的数字化管理解决方案。 1、开发海外仓系统要考虑的功能…...

计算机组成原理(Wrong Question)
目录 一、计算机系统概述 *1.1 计算机发展历程 1.2 计算机系统层次结构 1.3 计算机的性能指标 二、 数据的表示和运算 2.1 数制和编码 2.2 运算方法和运算电路 2.3 浮点数的表示与运算 三、存储系统 3.1 存储器概述 3.2 主存储器 3.3 主存储器与CPU的连接 3.4 外部…...

ACL2024 | AI的时空穿越记:大型语言模型共时推理的奇幻之旅!
作者:苏肇辰 标题:Living in the Moment: Can Large Language Models Grasp Co-Temporal Reasoning? 录取:ACL2024 Main 论文链接:https://arxiv.org/abs/2406.09072 代码链接:https://github.com/zhaochen0110/Cotem…...

从xxl-job源码中学习Netty的使用
1. 启动与Spring实例化 com.xxl.job.core.executor.impl.XxlJobSpringExecutor.java类 继承SmartInitializingSingleton 类,在afterSingletonsInstantiated 实例化后方法中 调用initJobHandlerMethodRepository 把所有的xxljob任务管理起来; private…...

人工智能发展历程了解和Tensorflow基础开发环境构建
目录 人工智能的三次浪潮 开发环境介绍 Anaconda Anaconda的下载和安装 下载说明 安装指导 模块介绍 使用Anaconda Navigator Home界面介绍 Environment界面介绍 使用Jupter Notebook 打开Jupter Notebook 配置默认目录 新建文件 两种输入模式 Conda 虚拟环境 添…...
makefile追加warning日志
在Makefile中,你不能直接“追加”warning日志到构建过程中,但你可以通过几种方式在构建时产生额外的警告或消息。以下是一些常用的方法: 使用echo或printf命令: 在Makefile的规则中,你可以使用echo或printf命令来输出警…...

不要直接使用unidefined 而使用void 0
为什么不要使用unidefined 而使用void 0? 在JavaScript中,undefined 和 void 0 都可以用来表示未定义的值,但它们在使用和上下文中有一些微妙的差异,这也是为什么有时可能会推荐使用 void 0 而不是直接使用 undefined。 全局污染ÿ…...
注解详解系列 - @Scope:Bean作用域管理
注解简介 在今天的注解详解系列中,我们将探讨Scope注解。Scope是Spring框架中的一个重要注解,用于定义Spring bean的作用域。通过指定bean的作用域,我们可以控制bean的生命周期和创建方式。 注解定义 Scope注解用于指定Spring bean的作用域…...

数学建模基础:数学建模概述
目录 前言 一、数学建模的步骤 二、模型的分类 三、模型评价指标 四、常见的数学建模方法 实际案例:线性回归建模 步骤 1:导入数据 步骤 2:数据预处理 步骤 3:建立线性回归模型 步骤 4:模型验证 步骤 5&…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...
变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析
一、变量声明设计:let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性,这种设计体现了语言的核心哲学。以下是深度解析: 1.1 设计理念剖析 安全优先原则:默认不可变强制开发者明确声明意图 let x 5; …...

STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

MMaDA: Multimodal Large Diffusion Language Models
CODE : https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA,它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构…...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...

PL0语法,分析器实现!
简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...
laravel8+vue3.0+element-plus搭建方法
创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill
视觉语言模型(Vision-Language Models, VLMs),为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展,机器人仍难以胜任复杂的长时程任务(如家具装配),主要受限于人…...