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

C++ 堆排序

C++ 堆排序

堆排序是一种基于二叉堆数据结构的排序算法,其原理如下:

  1. 构建最大堆:将待排序的数组看作一个完全二叉树,并通过调整节点的位置构建一个最大堆。最大堆满足每个父节点的值都大于或等于其子节点的值。构建最大堆的过程可以从最后一个非叶子节点开始,逐步向前,对每个节点进行下沉操作,使得子树满足最大堆的性质。

  2. 排序过程:构建完成最大堆后,将堆顶元素(即最大值)与数组的最后一个元素交换。然后,将堆的大小减1,再对堆顶元素执行下沉操作,以重新满足最大堆的性质。重复这个过程,直到堆的大小减少到1。最终,得到的数组就是有序的。

堆排序的关键操作是下沉(sink)和上浮(swim):

  • 下沉操作:将某个节点与其子节点中较大的节点交换位置,并递归地对交换后的子节点执行下沉操作,直到满足最大堆的性质。
  • 上浮操作:将某个节点与其父节点比较,如果节点的值大于父节点的值,则交换位置,并递归地对交换后的父节点执行上浮操作,直到满足最大堆的性质。

堆排序的时间复杂度为O(n log n),其中n是待排序数组的长度。构建最大堆的时间复杂度是O(n),排序过程需要进行n次下沉操作,每次下沉操作的时间复杂度是O(log n)。由于堆排序是原地排序算法,不需要额外的辅助空间,因此空间复杂度是O(1)。

需要注意的是,堆排序是不稳定的排序算法,即相等元素的相对顺序可能会发生改变。

#include <iostream>
using namespace std;void heapify(int arr[], int n, int i) {int largest = i;  // 将当前节点设置为最大值int left = 2 * i + 1;  // 左子节点索引int right = 2 * i + 2;  // 右子节点索引// 如果左子节点存在且大于根节点,则更新最大值索引if (left < n && arr[i] < arr[left]) {largest = left;}// 如果右子节点存在且大于根节点或左子节点,则更新最大值索引if (right < n && arr[largest] < arr[right]) {largest = right;}// 如果最大值不是根节点,则交换根节点和最大值,并继续调整堆if (largest != i) {swap(arr[i], arr[largest]);heapify(arr, n, largest);}
}void heapSort(int arr[], int n) {// 构建最大堆(从最后一个非叶子节点开始)for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 逐个将最大值移到数组末尾,并重新调整堆for (int i = n - 1; i > 0; i--) {swap(arr[0], arr[i]);  // 交换根节点和最后一个节点heapify(arr, i, 0);}
}int main() {int arr[] = {12, 11, 13, 5, 6, 7};int n = sizeof(arr) / sizeof(arr[0]);heapSort(arr, n);cout << "排序后的数组: ";for (int i = 0; i < n; i++) {cout << arr[i] << " ";}return 0;
}

相关文章:

C++ 堆排序

C 堆排序 堆排序是一种基于二叉堆数据结构的排序算法&#xff0c;其原理如下&#xff1a; 构建最大堆&#xff1a;将待排序的数组看作一个完全二叉树&#xff0c;并通过调整节点的位置构建一个最大堆。最大堆满足每个父节点的值都大于或等于其子节点的值。构建最大堆的过程可以…...

U3D记录之FBX纹理丢失问题

今天费老大劲从blender建了个模型&#xff0c;然后导出进去unity 发现贴图丢失 上网查了一下 首先blender导出要改设置 这个path mode要copy 然后unity加载纹理也要改设置 这里这个模型的纹理load要改成external那个模式 然后就有了&#xff0c;另外这个导出还有好多选项可…...

监测Nginx访问日志502情况后并做相应动作

今天带大家写一个比较实用的脚本哈 原理&#xff1a; 假设服务器环境为lnmp&#xff0c;近期访问经常出现502现象&#xff0c;且502错误在重启php-fpm服务后消失&#xff0c;因此需要编写监控脚本&#xff0c;一旦出现502&#xff0c;则自动重启php-fpm服务 场景&#xff1a; 1…...

【数据分享】1929-2023年全球站点的逐年平均风速(Shp\Excel\免费获取)

气象数据是在各项研究中都经常使用的数据&#xff0c;气象指标包括气温、风速、降水、能见度等指标&#xff0c;说到气象数据&#xff0c;最详细的气象数据是具体到气象监测站点的数据&#xff01; 有关气象指标的监测站点数据&#xff0c;之前我们分享过1929-2023年全球气象站…...

Android性能调优 - 应用安全问题

Android应用安全 1.组件暴露&#xff1a; 像比如ContentProvider,BroadcastReceiver&#xff0c;Activity等组件有android:exported属性&#xff1b; 如果是私有组件 android:exported “false”&#xff1b; 如果是公有组件 android:exported “true” 且进行权限控制&…...

C#的Char 结构的像IsLetterOrDigit(Char)等常见的方法

目录 一、Char 结构的方法 二、Char.IsLetterOrDigit 方法 1.Char.IsLetterOrDigit(Char)用法 2.IsLetterOrDigit(String, Int32)方法 三、Char.IsLetter 方法 1.IsLetter(Char) 2.IsLetter(String, Int32) 四、Char.IsDigit 方法 1. IsDigit(String, Int32) 2.IsDig…...

部分意图分类【LLM+RAG】

在生成人工智能领域工作最有价值的事情之一就是发现新兴技术如何融入新的解决方案。 举个例子&#xff1a;在为北美顶级金融服务公司之一设计对话式人工智能助手时&#xff0c;WillowTree 的数据和人工智能研究团队 (DART) 发现&#xff0c;将意图分类与大型语言模型 (LLM) 结合…...

1277. 统计全为 1 的正方形子矩阵

1277. 统计全为 1 的正方形子矩阵 题目链接&#xff1a;1277. 统计全为 1 的正方形子矩阵 代码如下&#xff1a; class Solution { public:int countSquares(vector<vector<int>>& matrix) {if(matrix.size()0||matrix[0].size()0) return 0;//dp[i][j]代表…...

Python 3 时间序列可视化指南

简介 时间序列分析属于统计学的一个分支&#xff0c;涉及对有序的、通常是时间性的数据进行研究。当适当应用时&#xff0c;时间序列分析可以揭示意想不到的趋势&#xff0c;提取有用的统计数据&#xff0c;甚至预测未来的趋势。因此&#xff0c;它被应用于许多领域&#xff0…...

[算法前沿]--059-大语言模型Fine-tuning踩坑经验之谈

前言 由于 ChatGPT 和 GPT4 兴起,如何让人人都用上这种大模型,是目前 AI 领域最活跃的事情。当下开源的 LLM(Large language model)非常多,可谓是百模大战。面对诸多开源本地模型,根据自己的需求,选择适合自己的基座模型和参数量很重要。选择完后需要对训练数据进行预处…...

【Docker】01 Docker安装与配置

文章目录 一、Docker二、离线安装Docker三、联网安装Docker3.1 下载YUM软件库文件3.2 安装epel-release3.3 安装yum-utils3.4 设置镜像仓库3.5 查看docker-ce所有版本3.6 安装Docker3.7 启动Docker3.8 查看Docker信息3.9 启动第一个容器 四、一些配置4.1 登录DockerHub4.2 镜像…...

Unity3d Shader篇(六)— BlinnPhong高光反射着色器

文章目录 前言一、BlinnPhong高光反射着色器是什么&#xff1f;1. BlinnPhong高光反射着色器的工作原理2. BlinnPhong高光反射着色器的优缺点优点缺点 3. 公式 二、使用步骤1. Shader 属性定义2. SubShader 设置3. 渲染 Pass4. 定义结构体和顶点着色器函数5. 片元着色器函数 三…...

Go-zero微服务个人探究之路(十二)定时任务的选择调研

前言 很多时候后台需要做定时任务的需求&#xff0c;笔者的项目采用go-zero框架微服务框架&#xff0c;需要做定时任务&#xff0c;于是做了如下方法调研&#xff0c;共有大概三种主要选择 方案 难度总体由容易到复杂 go的timer库 通过Go的标准库time中的Ticker和Tick功能…...

Java中,List、Map和Set的区别是什么?

在Java中&#xff0c;List、Map和Set是三种常用的集合类型&#xff0c;它们之间的主要区别如下&#xff1a; 1、List List是有序集合&#xff0c;它可以包含重复元素。 List中的元素是按照插入顺序排列的&#xff0c;可以通过索引访问每个元素。 Java中常见的List实现类有A…...

Google刚刚推出了图神经网络Tensorflow-GNN

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…...

链表基础知识汇总

链表 链表是一种基本的数据结构&#xff0c;是由一系列节点组成的集合。每个节点包含两个部分&#xff1a;值和指向下一个节点的指针。链表中的节点可以动态地添加、删除&#xff0c;其大小可以根据需要进行扩展或缩小。 链表通常用于处理不固定长度的数据结构&#xff0c;具有…...

Educational Codeforces Round 2(远古edu计划)

A. 恶心模拟。。 模拟一下分类即可 数字类&#xff0c;数字0&#xff0c;或者都是数字 字母类&#xff0c;字母空的也是字母&#xff0c;有字母就是字母 #include<bits/stdc.h> #define INF 1e9 using namespace std; typedef long long ll; const int N2e59; strin…...

【Tauri】(1):使用Tauri1.5版本,进行桌面应用开发,在windows,linux进行桌面GUI应用程序开发,可以打包成功,使用 vite 最方便

1&#xff0c;视频地址&#xff1a; https://www.bilibili.com/video/BV1Pz421d7s4/ 【Tauri】&#xff08;1&#xff09;&#xff1a;使用Tauri1.5版本&#xff0c;进行桌面应用开发&#xff0c;在windows&#xff0c;linux进行桌面GUI应用程序开发&#xff0c;可以打包成功&…...

「Linux」软件安装

MySQL5.7在CentOS安装 安装 配置yum仓库 更新密钥&#xff1a;rpm --import https://repo.mysql.com/RPM-GPG-KEY-mysql-2022安装MySQL yum库&#xff1a;rpm -Uvh http://repo.mysql.com//mysql57-community-release-el7-7.noarch.rpm使用yum安装MySQL&#xff1a;yum -y in…...

Ubuntu Desktop - Terminal 输出全部选中 + 复制

Ubuntu Desktop - Terminal 输出全部选中 复制 1. Terminal2. Terminal 最大化3. Edit -> Select All4. Copy & PasteReferences 1. Terminal 2. Terminal 最大化 3. Edit -> Select All 4. Copy & Paste Edit -> Copy or Shift Ctrl C Edit -> Paste…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

Python Ovito统计金刚石结构数量

大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

解读《网络安全法》最新修订,把握网络安全新趋势

《网络安全法》自2017年施行以来&#xff0c;在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂&#xff0c;网络攻击、数据泄露等事件频发&#xff0c;现行法律已难以完全适应新的风险挑战。 2025年3月28日&#xff0c;国家网信办会同相关部门起草了《网络安全…...