当前位置: 首页 > news >正文

【数据结构】第十八弹---C语言实现堆排序

个人主页: 熬夜学编程的小林

💗系列专栏: 【C语言详解】 【数据结构详解】【C++详解】

目录

1、堆排序

1.1、基本思想

1.2、初步代码实现

1.3、代码优化

1.4、代码测试

总结


1、堆排序

在博主数据结构第十二弹---堆的应用有详细讲解堆排序喔~~~

数据结构第十二弹---堆的应用https://blog.csdn.net/2201_75584283/article/details/135348207icon-default.png?t=N7T8https://blog.csdn.net/2201_75584283/article/details/135348207

1.1、基本思想

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆,排降序建小堆

为什么升序用到的是大堆呢?

因为:大堆的堆顶是最大的数,可以将其放在数组尾,然后再通过向下调整算法找到次大的数。而小堆的堆顶是最小的数,需要放在第一个位置,如果用原来的堆找不到次小的数,而重新建堆则会更加繁琐。

降序用小堆同理。

动图如下:

1.2、初步代码实现

堆排序的实现可以分为两部分:构建最大堆(或最小堆)和执行排序过程。

注意:此处我们实现的是大堆!!!

第一步:建堆

我们此处是对数组内部的数进行排序,那么怎样才能创建成大堆呢?

这里我们可以使用向上调整算法,从第二个数开始遍历数组,如果不满足大堆则交换父子元素。

for (int i = 1; i < n; i++)
{AjustUp(a, i);
}

大堆向上调整:

  1. 将被调整的数值与其父节点比较,若是大于父节点,则与父节点交换。
  2. 若子节点下标为child,父节点下标为(child - 1) / 2。
  3. 当子节点小于父节点时,或者当子节点已经为堆顶时,停止比较。

代码实现:

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)

第二步:执行排序操作

进行了向上调整之后,此时的数组就是一个大堆了,要怎样才能达到升序呢?

  1. 使用大根堆选出最大的数,放在数组的最后一个位置,依次选出进行排序。
  2. 将堆顶和最后一个数交换。
  3. 然后将新堆顶向下调整,形成堆。
  4. 向下调整时,注意交换后的最后位置不在新堆里,所以要下标要减一。
  5. 没有对堆结构造成破坏,不用对每个数都调整。
//2.向下调整 O(N*logN)
int end = n - 1;
while (end > 0) //从最后一个位置开始交换并调整
{Swap(&arr[0], &arr[end]);AdjustDown(arr, end, 0);//此处为大根堆向下调整方式end--;
}

 大堆向下调整:

  1. 将被调整的数值与其最大的子节点比较,若是小于最大的子节点,则与该子节点交换。
  2. 若父节点下标为parent,左子节点下标为 parent * 2 + 1,右子节点的下标为 parent * 2 + 2。
  3. 获取最大的子节点时,可以先将左子节点作为最大节点,再与右子节点比较,若是大于右子节点,则将左子节点下标加1得到右子节点下标。
  4. 再循环体内比较左右子节点之前,要先判断右子节点存在,防止堆最后一个节点是左子节点造成越界访问。
  5. 当子节点小于父节点时,或者当子节点超过堆的范围时,停止比较。

//向下调整算法 大堆
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;}}
}

小堆向下调整:

  1. 将被调整的数值与其最小的子节点比较,若是大于最小的子节点,则与该子节点交换。
  2. 将小根堆向下调整时左右子节点的比较条件和父节点与子节点的比较改为小于即可。
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),因此我们在堆排序的时候也可以统一使用向下调整算法!!!

向下调整:

  1. 向下调整是从后往前调整,先将后面构成堆,再调整上面的节点。
  2. 以叶子节点作为根进行向下调整是完全没有必要的,叶子节点没有子节点,所以对最后一个叶子节点的父节点开始向下调整。
  3. 最后一个节点下标是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语言实现堆排序

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【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

解压的时候发现不能解压&#xff0c;报-bash: unzip: command not found 1、访问https://www.rpmfind.net/linux/rpm2html/search.php?queryzip&submitSearch…&systemcentos&arch#/ 2、输入zip和centos搜索&#xff0c;选择el7下载 3、输入unzip和centos搜索&am…...

Linux下lsof命令使用

目录 lsof 命令使用指南基本语法常用选项使用示例 lsof vs netstatlsofnetstat区别示例对比 lsof 命令使用指南 lsof (List Open Files) 是一个用于列出当前系统中打开文件的命令&#xff0c;适用于 Unix 和类 Unix 操作系统。它不仅可以列出常规文件&#xff0c;还可以列出打…...

基于ChatGPT的大型语言模型试用心得

近年来&#xff0c;ChatGPT这样的大型语言模型&#xff0c;它如同一颗冉冉升起的新星&#xff0c;迅速在商业、教育、娱乐等多个领域照亮了创新的天空&#xff0c;极大地革新了我们的工作与日常生活。 最近我发现一些国内用户也能自由访问的中文ChatGPT APP。这个平台不仅提供…...

Python 列表添加多个值(四种方法)

Python 列表添加多个值有多种方法,以下是其中几种实现方法: 一、使用extend()方法 Python 中列表对象有一个 extend() 方法,它可以一次性添加另一个列表中的所有元素到当前列表中。 例1: a = [1, 2, 3] b = [4, 5, 6] a.extend(b)...

VMware RedHat虚拟机磁盘扩容(添加磁盘和扩展磁盘)

前言 自己的电脑上配一个虚拟机还是很有必要的&#xff0c;用起来比双系统方便一点&#xff0c;之前搞了100g的ubuntu没用到&#xff0c;后面重装redhat觉得随便搞个20g就够用了&#xff0c;后面用到之后就遇到磁盘不够用的情况&#xff0c;只能说情况允许的话&#xff0c;磁盘…...

最近,GPT-4o横空出世。对GPT-4o这一人工智能技术进行评价,包括版本间的对比分析、GPT-4o的技术能力以及个人整体感受等

GPT-4o是一款引人瞩目的人工智能技术&#xff0c;它在之前版本的基础上取得了长足的进步。本文将对GPT-4o进行评价&#xff0c;包括版本间的对比分析、GPT-4o的技术能力以及个人整体感受等。 首先&#xff0c;我们来进行GPT-4o与之前版本的对比分析。GPT-4o相较于GPT-3和GPT-2…...

C#面:C#支持多重继承么?

C#不支持多重继承。在C#中&#xff0c;一个类只能直接继承自一个基类。这是由于C#的设计目标之一是避免多重继承可能带来的复杂性和潜在的问题。 然而&#xff0c;C#提供了接口&#xff08;interface&#xff09;的概念来实现类似多重继承的功能。一个类可以实现多个接口&…...

细说MCU修改回调函数调用模式的方法

目录 1、硬件及工程 2、实现方法 &#xff08;1&#xff09;修改while(1)中的代码&#xff1a; &#xff08;2&#xff09;修改2 &#xff08;3&#xff09;修改3 &#xff08;4&#xff09;修改4 &#xff08;5&#xff09;修改5 3、下载并运行 在本文作者的文章中&a…...

Java共享台球室无人系统支持微信小程序+微信公众号

共享台球室无人系统 &#x1f3b1; 创新台球体验 近年来&#xff0c;共享经济如火如荼&#xff0c;从共享单车到共享汽车&#xff0c;无一不改变着我们的生活方式。而如今&#xff0c;这一模式已经渗透到了更多领域&#xff0c;共享台球室便是其中之一。不同于传统的台球室&a…...

如何开发一个海外仓系统?难度在哪,怎么选择高性价解决方案

作为海外仓管理的重要工具&#xff0c;海外仓系统的实际应用价值还是非常高的。为了让大家能更好的理解wms海外仓系统&#xff0c;今天会介绍海外仓系统开发的逻辑架构&#xff0c;以及作为海外仓企业要怎么确定高性价比的数字化管理解决方案。 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的时空穿越记:大型语言模型共时推理的奇幻之旅!

作者&#xff1a;苏肇辰 标题&#xff1a;Living in the Moment: Can Large Language Models Grasp Co-Temporal Reasoning? 录取&#xff1a;ACL2024 Main 论文链接&#xff1a;https://arxiv.org/abs/2406.09072 代码链接&#xff1a;https://github.com/zhaochen0110/Cotem…...

从xxl-job源码中学习Netty的使用

1. 启动与Spring实例化 com.xxl.job.core.executor.impl.XxlJobSpringExecutor.java类 继承SmartInitializingSingleton 类&#xff0c;在afterSingletonsInstantiated 实例化后方法中 调用initJobHandlerMethodRepository 把所有的xxljob任务管理起来&#xff1b; private…...

人工智能发展历程了解和Tensorflow基础开发环境构建

目录 人工智能的三次浪潮 开发环境介绍 Anaconda Anaconda的下载和安装 下载说明 安装指导 模块介绍 使用Anaconda Navigator Home界面介绍 Environment界面介绍 使用Jupter Notebook 打开Jupter Notebook 配置默认目录 新建文件 两种输入模式 Conda 虚拟环境 添…...

makefile追加warning日志

在Makefile中&#xff0c;你不能直接“追加”warning日志到构建过程中&#xff0c;但你可以通过几种方式在构建时产生额外的警告或消息。以下是一些常用的方法&#xff1a; 使用echo或printf命令&#xff1a; 在Makefile的规则中&#xff0c;你可以使用echo或printf命令来输出警…...

不要直接使用unidefined 而使用void 0

为什么不要使用unidefined 而使用void 0? 在JavaScript中&#xff0c;undefined 和 void 0 都可以用来表示未定义的值&#xff0c;但它们在使用和上下文中有一些微妙的差异&#xff0c;这也是为什么有时可能会推荐使用 void 0 而不是直接使用 undefined。 全局污染&#xff…...

注解详解系列 - @Scope:Bean作用域管理

注解简介 在今天的注解详解系列中&#xff0c;我们将探讨Scope注解。Scope是Spring框架中的一个重要注解&#xff0c;用于定义Spring bean的作用域。通过指定bean的作用域&#xff0c;我们可以控制bean的生命周期和创建方式。 注解定义 Scope注解用于指定Spring bean的作用域…...

数学建模基础:数学建模概述

目录 前言 一、数学建模的步骤 二、模型的分类 三、模型评价指标 四、常见的数学建模方法 实际案例&#xff1a;线性回归建模 步骤 1&#xff1a;导入数据 步骤 2&#xff1a;数据预处理 步骤 3&#xff1a;建立线性回归模型 步骤 4&#xff1a;模型验证 步骤 5&…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...