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

排序算法---堆排序

原创不易,转载请注明出处。欢迎点赞收藏~

堆排序(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函数对数组进行排序。排序后,打印出排序后的数组。

请注意,这只是一个简单的堆排序示例,实际应用中可能需要考虑更多的边界情况和错误处理。

运行如上代码,你可以看到以下输出:

相关文章:

排序算法---堆排序

原创不易&#xff0c;转载请注明出处。欢迎点赞收藏~ 堆排序&#xff08;Heap Sort&#xff09;是一种基于二叉堆数据结构的排序算法。它将待排序的元素构建成一个最大堆&#xff08;或最小堆&#xff09;&#xff0c;然后逐步将堆顶元素与堆的最后一个元素交换位置&#xff0c…...

Java字符串(包含字母和数字)通用排序

说明&#xff1a;本文章是之前查到的一篇安卓版的&#xff0c;具体原文路径忘记了。稍微改了一点&#xff0c;挺符合业务使用的&#xff01; 一、看代码 /*** 包含数字的字符串进行比较&#xff08;按照从小到大排序&#xff09;*/private static Integer compareString(Stri…...

【Spring】springmvc如何处理接受http请求

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

2024年安全员-B证证模拟考试题库及安全员-B证理论考试试题

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2024年安全员-B证证模拟考试题库及安全员-B证理论考试试题是由安全生产模拟考试一点通提供&#xff0c;安全员-B证证模拟考试题库是根据安全员-B证最新版教材&#xff0c;安全员-B证大纲整理而成&#xff08;含2024年…...

redis过期淘汰策略、数据过期策略与持久化方式

redis的过期淘汰策略 redis过期淘汰策略有很多,默认是no-eviction 不删除任何数据,内存不足存入会直接报错,可以在redis配置文件中进行设置,其中有两个非常重要的概念,LRU与LFU LRU表示最近最少使用,LFU为最少频率使用 又按照volatile已设置过期时间的数据集和allkeys所有数…...

Oracle Vagrant Box 扩展根文件系统

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

TDengine用户权限管理

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

推荐一款开源的跨平台划词翻译和OCR翻译软件:Pot

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

spring boot学习第十一篇:发邮件

1、pom.xml文件内容如下&#xff08;是我所有学习内容需要的&#xff0c;不再单独分出来&#xff0c;包不会冲突&#xff09;&#xff1a; <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"…...

Linux中ps/kill/execl的使用

ps命令&#xff1a; ps -aus或者ps -ajx或者 ps -ef可以查看有哪些进程。加上 | grep "xxx" 可以查看名为”xxx"的进程。 ps -aus | grep "xxx" kill命令&#xff1a; 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产品很多&#xff0c;操作方式各有不同&#xff0c;于是JAVA提供了一套规则 ——JMS&#xff0c;用于操作消息中间件。JMS即Java消息服务 &#xff08;JavaMessage Service&#xff09;应用程序接口&#xff0c;是一个Java平台中关于面 向消息中间件的…...

【工作学习 day04】 9. uniapp 页面和组件的生命周期

问题描述 uniapp常用的有&#xff1a;页面和组件&#xff0c;并且页面和组件各自有各自的生命周期函数&#xff0c;那么在页面/组件请求数据时&#xff0c;是用created呢&#xff0c;还是用onLoad呢&#xff1f; 先说结论: 组件使用组件的生命周期&#xff0c;页面使用页面的…...

Mysql-数据库优化-客户端连接参数

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

【十二】【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镜像就是一个只读的模板。 例如&#xff1a;一个镜像可以包含一个完整的ubuntu操作系统环境&#xff0c;里面仅安装了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变懒这件事又有了最新解释了。 这两天&#xff0c;推特用户Dylan Patel发文表示&#xff1a; 你想知道为什么 ChatGPT 和 6 个月前相比会如此糟糕吗&#xff1f; 那是因为ChatGPT系统Prompt是竟然包含1700 tokens&#xff0c;看看这个prompt里面有多…...

书生·浦语大模型第三课作业

基础作业&#xff1a; 复现课程知识库助手搭建过程 (截图) 进阶作业&#xff1a; 选择一个垂直领域&#xff0c;收集该领域的专业资料构建专业知识库&#xff0c;并搭建专业问答助手&#xff0c;并在 OpenXLab 上成功部署&#xff08;截图&#xff0c;并提供应用地址&#x…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

Golang——9、反射和文件操作

反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一&#xff1a;使用Read()读取文件2.3、方式二&#xff1a;bufio读取文件2.4、方式三&#xff1a;os.ReadFile读取2.5、写…...

Linux部署私有文件管理系统MinIO

最近需要用到一个文件管理服务&#xff0c;但是又不想花钱&#xff0c;所以就想着自己搭建一个&#xff0c;刚好我们用的一个开源框架已经集成了MinIO&#xff0c;所以就选了这个 我这边对文件服务性能要求不是太高&#xff0c;单机版就可以 安装非常简单&#xff0c;几个命令就…...

API网关Kong的鉴权与限流:高并发场景下的核心实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中&#xff0c;API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关&#xff0c;Kong凭借其插件化架构…...

针对药品仓库的效期管理问题,如何利用WMS系统“破局”

案例&#xff1a; 某医药分销企业&#xff0c;主要经营各类药品的批发与零售。由于药品的特殊性&#xff0c;效期管理至关重要&#xff0c;但该企业一直面临效期问题的困扰。在未使用WMS系统之前&#xff0c;其药品入库、存储、出库等环节的效期管理主要依赖人工记录与检查。库…...

Qt的学习(一)

1.什么是Qt Qt特指用来进行桌面应用开发&#xff08;电脑上写的程序&#xff09;涉及到的一套技术Qt无法开发网页前端&#xff0c;也不能开发移动应用。 客户端开发的重要任务&#xff1a;编写和用户交互的界面。一般来说和用户交互的界面&#xff0c;有两种典型风格&…...