国内老牌的室内设计网站/百度高级搜索网址
✨个人主页: 熬夜学编程的小林
💗系列专栏: 【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&…...

人工智能大模型之开源大语言模型汇总(国内外开源项目模型汇总)
开源大语言模型完整列表 Large Language Model (LLM) 即大规模语言模型,是一种基于深度学习的自然语言处理模型,它能够学习到自然语言的语法和语义,从而可以生成人类可读的文本。 所谓"语言模型",就是只用来处理语言文…...

数据结构之B树
引言 在计算机科学中,数据结构是用于组织和存储数据的关键工具。其中,B树(B-tree)作为一种自平衡的树形数据结构,被广泛应用于数据库和文件系统中,以提高查找、插入、删除和范围查询的效率。本文将深入探讨…...

双色球预测算法(Java),——森林机器学习、时间序列
最近AI很火,老想着利用AI的什么算法,干点什么有意义的事情。其中之一便想到了双色球,然后让AI给我预测,结果基本都是简单使用随机算法列出了几个数字。 额,,,,咋说呢,双…...

【计算机网络篇】数据链路层(11)在数据链路层扩展以太网
文章目录 🍔使用网桥在数据链路层扩展以太网🥚网桥的主要结构和基本工作原理🎈网桥的主要结构🔎网桥转发帧的例子🔎网桥丢弃帧的例子🔎网桥转发广播帧的例子 🥚透明网桥🔎透明网桥的…...

Ubuntu20.04 使用scrapy-splash爬取动态网页
我们要先安装splash服务,使用dock安装,如果dock没有安装,请参考我的上一篇博文: 按照官方文档:https://splash.readthedocs.io/en/stable/install.html 1.下载splash sudo docker pull scrapinghub/splash2.安装scrapy…...

Function:控制继电器上下电,上电后adb登录,copy配置文件
import serial import time import datetime import subprocess import osdef append_to_txt(file_path, content):if os.path.exists(file_path):with open(file_path, a) as file: # 使用 a 模式打开文件进行追加file.write(content \n) # 追加内容,并换行else…...

香港电讯高可用网络助力企业变革金融计算
客户背景 客户是一家金融行业知名的量化私募对冲基金公司,专注于股票、期权、期货、债券等主要投资市场,在量化私募管理深耕多年,目前资管规模已达数百亿级,在国内多个城市均设有办公地点。 客户需求 由于客户业务倚重量化技术…...

LDR6020一拖二快充线:多设备充电新选择
随着科技的快速发展,我们的日常生活中越来越多地依赖于智能设备。然而,每当手机、平板或其他移动设备电量告急时,我们总是需要寻找合适的充电线进行充电。为了解决这一痛点,市场上出现了一款备受瞩目的新产品——LDR6020一拖二快充…...

电脑ffmpeg.dll丢失原因解析,找不到ffmpeg.dll的5种解决方法
在数字化时代,多媒体文件的处理已经成为我们日常生活和工作中不可或缺的一部分。在计算机使用过程中,丢失ffmpeg.dll文件是一个特定但常见的问题,尤其是对于那些经常处理视频编解码任务的用户来说。下面小编讲全面分析ffmpeg.dll丢失原因以及…...

手机网站制作软件是哪些
手机网站制作软件是一种用于设计、开发和创建适用于移动设备的网站的软件工具。随着移动互联网时代的到来,越来越多的用户开始使用手机浏览网页和进行在线交流,因此,手机网站制作软件也逐渐成为了市场上的热门工具。 1. Adobe Dreamweaver&am…...