排序算法---堆排序
原创不易,转载请注明出处。欢迎点赞收藏~
堆排序(Heap Sort)是一种基于二叉堆数据结构的排序算法。它将待排序的元素构建成一个最大堆(或最小堆),然后逐步将堆顶元素与堆的最后一个元素交换位置,并重新调整堆,使得剩余未排序部分继续满足堆的性质。通过不断重复这个过程,最终将得到一个有序的序列。
具体步骤如下:
1. 构建初始堆:首先将待排序序列看作是完全二叉树,从最后一个非叶子节点开始,逐个向上调整节点,使得以每个节点为根的子树都满足堆的性质。
2. 排序:将堆顶元素与待排序序列的最后一个元素交换位置,然后将剩下的 n-1 个元素重新调整为堆。重复这个过程,直到堆中只剩下一个元素,即完成排序。
堆排序的关键操作是堆的调整,有两种方式可以实现:
1. 自顶向下调整(Down-Heapify):从根节点开始,不断将根节点与其左右子节点中较大(或较小)的交换,直到满足堆的性质。
2. 自底向上调整(Up-Heapify):从最后一个非叶子节点开始往上逐个调整,将每个节点与其左右子节点中较大(或较小)的交换,直到满足堆的性质。
堆排序的时间复杂度为O(nlogn),其中n是待排序元素的个数。堆的构建过程需要O(n)的时间,每次调整堆的操作需要O(logn)的时间,共需要进行n-1次调整。所以总体时间复杂度是O(nlogn)。
堆排序的空间复杂度为O(1),它是一种原地排序算法,不需要额外的存储空间。
堆排序具有以下特点:
稳定性:堆排序是一种不稳定的排序算法,即相同元素的相对位置可能会发生改变。
适应性:堆排序适用于大规模数据的排序,因为它的时间复杂度不会随数据规模增大而增加,且不需要额外的存储空间。
不适应性:堆排序不适用于小规模数据的排序,因为它的常数因子较大,且堆的构建过程需要较多的比较和交换操作。
需要注意的是,堆排序对于相同元素的排序可能会打乱它们的原始相对顺序,这是由于堆本身的性质所决定的。如果要保持相同元素的相对顺序不变,可以采用稳定的排序算法来代替堆排序。
以下是一个使用C语言实现堆排序的示例代码:
#include <stdio.h>// 交换两个元素的值
void swap(int *a, int *b)
{int temp = *a;*a = *b;*b = temp;
}// 调整最大堆,使根节点为最大值
void max_heapify(int arr[], int n, int i)
{int largest = i; // 初始化最大值为根节点int left = 2 * i + 1; // 左子节点索引int right = 2 * i + 2; // 右子节点索引// 如果左子节点大于根节点,更新最大值为左子节点if (left < n && arr[left] > arr[largest])largest = left;// 如果右子节点大于当前最大值,更新最大值为右子节点if (right < n && arr[right] > arr[largest])largest = right;// 如果最大值不是根节点,则交换根节点和最大值if (largest != i){swap(&arr[i], &arr[largest]);// 递归调整交换后的子树max_heapify(arr, n, largest);}
}// 堆排序函数
void heap_sort(int arr[], int n)
{// 构建最大堆(初始状态)for (int i = n / 2 - 1; i >= 0; i--)max_heapify(arr, n, i);// 逐个将堆顶元素移至末尾,并重新调整堆for (int i = n - 1; i > 0; i--){// 将堆顶元素(最大值)与当前未排序部分的最后一个元素交换swap(&arr[0], &arr[i]);// 对剩余元素进行调整,使其满足最大堆性质max_heapify(arr, i, 0);}
}int main()
{int arr[] = {12, 11, 13, 5, 6, 7};int n = sizeof(arr) / sizeof(arr[0]);printf("排序前的数组:\n");for (int i = 0; i < n; i++){printf("%d ", arr[i]);}heap_sort(arr, n);printf("\n排序后的数组: \n");for (int i = 0; i < n; i++){printf("%d ", arr[i]);}putchar('\n');return 0;
}
这个示例中实现了堆排序算法。代码首先定义了两个辅助函数:swap用于交换两个元素的值,max_heapify用于调整最大堆。
max_heapify函数接收一个数组、堆的大小n和要调整的节点索引i作为参数。该函数首先将最大值初始化为当前节点(根节点),然后比较左子节点和右子节点的值,更新最大值。如果最大值不是根节点,则将其与根节点交换,并递归调用max_heapify来保持堆的性质。
heap_sort函数首先构建最大堆(通过循环调用max_heapify),然后逐个将堆顶元素(最大值)移动到未排序部分的末尾,并重新调整堆。在每次迭代中,通过swap操作将最大值放在数组的末尾,并对剩余元素进行调整,使其满足最大堆的性质。
最后,main函数创建一个包含一些无序元素的数组,并调用heap_sort函数对数组进行排序。排序后,打印出排序后的数组。
请注意,这只是一个简单的堆排序示例,实际应用中可能需要考虑更多的边界情况和错误处理。
运行如上代码,你可以看到以下输出:
相关文章:

排序算法---堆排序
原创不易,转载请注明出处。欢迎点赞收藏~ 堆排序(Heap Sort)是一种基于二叉堆数据结构的排序算法。它将待排序的元素构建成一个最大堆(或最小堆),然后逐步将堆顶元素与堆的最后一个元素交换位置,…...
Java字符串(包含字母和数字)通用排序
说明:本文章是之前查到的一篇安卓版的,具体原文路径忘记了。稍微改了一点,挺符合业务使用的! 一、看代码 /*** 包含数字的字符串进行比较(按照从小到大排序)*/private static Integer compareString(Stri…...

【Spring】springmvc如何处理接受http请求
目录 编辑 1. 背景 2. web项目和非web项目 3. 环境准备 4. 分析链路 5. 总结 1. 背景 今天开了一篇文章“SpringMVC是如何将不同的Request路由到不同Controller中的?”;看完之后突然想到,在请求走到mvc 之前服务是怎么知道有请求进来…...

2024年安全员-B证证模拟考试题库及安全员-B证理论考试试题
题库来源:安全生产模拟考试一点通公众号小程序 2024年安全员-B证证模拟考试题库及安全员-B证理论考试试题是由安全生产模拟考试一点通提供,安全员-B证证模拟考试题库是根据安全员-B证最新版教材,安全员-B证大纲整理而成(含2024年…...
redis过期淘汰策略、数据过期策略与持久化方式
redis的过期淘汰策略 redis过期淘汰策略有很多,默认是no-eviction 不删除任何数据,内存不足存入会直接报错,可以在redis配置文件中进行设置,其中有两个非常重要的概念,LRU与LFU LRU表示最近最少使用,LFU为最少频率使用 又按照volatile已设置过期时间的数据集和allkeys所有数…...

Oracle Vagrant Box 扩展根文件系统
需求 默认的Oracle Database 19c Vagrant Box的磁盘为34GB。 最近在做数据库升级实验,加之导入AWR dump数据,导致空间不够。 因此需要对磁盘进行扩容。 扩容方法1:预先扩容 此方法参考文档Vagrant, how to specify the disk size?。 指…...

TDengine用户权限管理
Background 官方文档关于用户管理没有很详细的介绍,只有零碎的几条,这里记录下方便后面使用。官方文档:https://docs.taosdata.com/taos-sql/show/#show-users 1、查看用户 show users;super 1,表示超级用户权限 0,表…...

推荐一款开源的跨平台划词翻译和OCR翻译软件:Pot
Pot简介 一款开源的跨平台划词翻译和OCR翻译软件 下载安装指南 根据你的机器型号下载对应版本,下载完成后双击安装即可。 使用教程 Pot具体功能如下: 划词翻译输入翻译外部调用鼠标选中需要翻译的文本,按下设置的划词翻译快捷键即可按下输…...

spring boot学习第十一篇:发邮件
1、pom.xml文件内容如下(是我所有学习内容需要的,不再单独分出来,包不会冲突): <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"…...

Linux中ps/kill/execl的使用
ps命令: ps -aus或者ps -ajx或者 ps -ef可以查看有哪些进程。加上 | grep "xxx" 可以查看名为”xxx"的进程。 ps -aus | grep "xxx" kill命令: kill -9 pid 杀死某个进程 kill -l 查看系统有哪些信号 execl函数&#…...

【web前端开发】HTML及CSS简单页面布局练习
案例一 网页课程 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" content"widthdevice-wi…...

2.7日学习打卡----初学RabbitMQ(二)
2.7日学习打卡 JMS 由于MQ产品很多,操作方式各有不同,于是JAVA提供了一套规则 ——JMS,用于操作消息中间件。JMS即Java消息服务 (JavaMessage Service)应用程序接口,是一个Java平台中关于面 向消息中间件的…...

【工作学习 day04】 9. uniapp 页面和组件的生命周期
问题描述 uniapp常用的有:页面和组件,并且页面和组件各自有各自的生命周期函数,那么在页面/组件请求数据时,是用created呢,还是用onLoad呢? 先说结论: 组件使用组件的生命周期,页面使用页面的…...

Mysql-数据库优化-客户端连接参数
客户端参数 原文地址 # 连接池配置 # 初始化连接数 spring.datasource.druid.initial-size1 # 最小空闲连接数,一般设置和initial-size一致 spring.datasource.druid.min-idle1 # 最大活动连接数,一个数据库能够支撑最大的连接数是多少呢? …...

【十二】【C++】vector用法的探究
vector类创建对象 /*vector类创建对象*/ #if 1 #define _CRT_SECURE_NO_WARNINGS#include <iostream> using namespace std; #include <vector> #include <algorithm> #include <crtdbg.h>class Date {public:Date(int year 1900, int month 1, int …...
Docker 基本介绍
Docker 基本介绍 镜像 Docker镜像就是一个只读的模板。 例如:一个镜像可以包含一个完整的ubuntu操作系统环境,里面仅安装了Apache或用户需要的其它应用 程序。 镜像可以用来创建Docker容器。Docker提供了一个很简单的机制来创建镜像或者更新现有的镜…...
CentOS 7 安装 install abiword
安装 1.下载noarch安装包 wget http://repo.iotti.biz/CentOS/7/noarch/lux-release-7-1.noarch.rpm 2.安装noarch rpm -Uvh lux-release-7-1.noarch.rpm 3.安装abiword yum -y install abiword...
开源的直播平台
直播平台系统界面介绍 开源一套直播平台 私信可获取源码...

ChatGPT 变懒最新解释!或和系统Prompt太长有关
大家好我是二狗。 ChatGPT变懒这件事又有了最新解释了。 这两天,推特用户Dylan Patel发文表示: 你想知道为什么 ChatGPT 和 6 个月前相比会如此糟糕吗? 那是因为ChatGPT系统Prompt是竟然包含1700 tokens,看看这个prompt里面有多…...

书生·浦语大模型第三课作业
基础作业: 复现课程知识库助手搭建过程 (截图) 进阶作业: 选择一个垂直领域,收集该领域的专业资料构建专业知识库,并搭建专业问答助手,并在 OpenXLab 上成功部署(截图,并提供应用地址&#x…...

国防科技大学计算机基础课程笔记02信息编码
1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...
作为测试我们应该关注redis哪些方面
1、功能测试 数据结构操作:验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化:测试aof和aof持久化机制,确保数据在开启后正确恢复。 事务:检查事务的原子性和回滚机制。 发布订阅:确保消息正确传递。 2、性…...
【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error
在前端开发中,JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作(如 Promise、async/await 等),开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝(r…...
DiscuzX3.5发帖json api
参考文章:PHP实现独立Discuz站外发帖(直连操作数据库)_discuz 发帖api-CSDN博客 简单改造了一下,适配我自己的需求 有一个站点存在多个采集站,我想通过主站拿标题,采集站拿内容 使用到的sql如下 CREATE TABLE pre_forum_post_…...
前端调试HTTP状态码
1xx(信息类状态码) 这类状态码表示临时响应,需要客户端继续处理请求。 100 Continue 服务器已收到请求的初始部分,客户端应继续发送剩余部分。 2xx(成功类状态码) 表示请求已成功被服务器接收、理解并处…...
数据库正常,但后端收不到数据原因及解决
从代码和日志来看,后端SQL查询确实返回了数据,但最终user对象却为null。这表明查询结果没有正确映射到User对象上。 在前后端分离,并且ai辅助开发的时候,很容易出现前后端变量名不一致情况,还不报错,只是单…...