排序算法-堆积树排序法(HeapSort)
目录
排序算法-堆积树排序法(HeapSort)
1、说明
2、算法分析
3、C++代码
排序算法-堆积树排序法(HeapSort)
1、说明
堆积树排序法是选择排序法的改进版,可以减少在选择排序法中的比较次数,进而减少排序时间。堆积排序法用到了二叉树的技巧,是利用堆积树来完成排序的。堆积树是一种特殊的二叉树,可分为最大堆积树和最小堆积树两种。
最大堆积树满足以下3个条件:
- 它是一棵完全二叉树。
- 所有节点的值都大于或等于它左右子节点的值。
- 树根是堆积树中最大的。
最小堆积树具备以下3个条件:
- 它是一棵完全二叉树。
- 所有节点的值都小于或等于它左右子节点的值。
- 树根是堆积树中最小的。
2、算法分析
- 在所有情况下,时间复杂度均为
。
- 堆积排序法不是稳定排序法。
- 只需要一个额外的空间,空间复杂度为
。
3、C++代码
#include<iostream>
#include<iomanip>
using namespace std;void Print(int* data, int size) {for (int i = 1; i < size; i++)cout << "[" << setw(2) << data[i] << "] ";cout << endl;
}void Swap(int& i, int& j) {int temp = i;i = j;j = temp;
}void ad_heap(int* data, int i, int size) {int j = 2 * i;int temp = data[i];int post = 0;while (j <= size && post == 0){if (j < size) {if (data[j] < data[j + 1])j++;}if (temp >= data[j])post = 1;else {data[j / 2] = data[j];j *= 2;}}data[j / 2] = temp;
}void Heap(int* data, int size) {for (int i = (size / 2); i > 0; i--)ad_heap(data, i, size - 1);for (int i = size - 2; i > 0; i--) {Swap(data[1], data[i + 1]);ad_heap(data, 1, i);}
}int main() {int data[9] = { 0,5,6,4,8,3,2,7,1 };int size = 9;cout << "原始数据:";Print(data, size);Heap(data, size);cout << "排序结果:";Print(data, size);return 0;
}
输出结果

相关文章:
排序算法-堆积树排序法(HeapSort)
目录 排序算法-堆积树排序法(HeapSort) 1、说明 2、算法分析 3、C代码 排序算法-堆积树排序法(HeapSort) 1、说明 堆积树排序法是选择排序法的改进版,可以减少在选择排序法中的比较次数,进而减少排序…...
名词解释 MongoDB
MongoDB 是一个面向文档的数据库管理系统,它不使用传统的表格结构,而是将数据组织成类似文档的形式,通常使用JSON格式。 文档数据库:数据以文档的形式存储,每个文档可以包含不同的字段,就像一个文件可以包…...
Look Back(cf div3 905)
题意:给你一个长度为n((1≤n≤10^5)数组a[],你可以进行一个操作 使a[i]a[i]*2,问最少经过多少次这样的操作使的a[]不递减,a[i]>a[i-1]。 输入样例: 6 1 1 2 1 1 3 1 2 1 4 2 3 2 1 5 4 5 4 5 4 10 1 7 7 2 3 4 3 2 1 100 输出…...
Spring框架的发展历程
Spring框架的发展历程 自2004年以来,Spring框架已经成为Java开发人员最受欢迎的开源框架之一。它提供了一个全面的编程和配置模型,旨在简化企业级Java应用程序的开发过程。本文将详细介绍Spring框架的发展历程,以及它如何为Java开发人员提供…...
vue 级联查询5级--省/市/区/街道/社区
<template> <div> 1234 <el-select v-model="provinceVal" @change="selectProvinceFn" placeholder="请选择"> <el-option v-for="item in provinceList" :key="item.code" :label="item.name&q…...
C++并发与多线程(8) | 互斥量
一、互斥量(mutex)的基本概念 互斥量(Mutex)是一种用于多线程编程的同步机制,用于管理共享资源的访问,以确保线程之间不会同时访问某个共享资源,从而避免竞态条件(Race Condition)和数据损坏。下面是互斥量的基本概念: 互斥性(Mutual Exclusion):互斥量用于确保一…...
Power BI 傻瓜入门 3. 选择Power BI的版本
本章内容包括: Excel与Power BI的比较选择Power BI的桌面版和服务版之间的差异了解Microsoft提供的许可选项 挑选正确版本的Power BI可能就像参观世界上最大的糖果店:你可以从许多细微差别的替代品中进行选择。选择可以归结为想要、需要、规模…...
BadNets:基于数据投毒的模型后门攻击代码(Pytorch)以MNIST为例
加载数据集 # 载入MNIST训练集和测试集 transform transforms.Compose([transforms.ToTensor(),]) train_loader datasets.MNIST(rootdata,transformtransform,trainTrue,downloadTrue) test_loader datasets.MNIST(rootdata,transformtransform,trainFalse) # 可视化样本 …...
freeRTOS内部机制——栈的作用
上图中*pa 和*pb分别为R0,R1,调用C函数时,第一个参数保存在R0中第二个参数保存在R1中。这是约定。 指令保存在哪里? 指令保存在flash上面 LR等于什么? LR是返回地址,函数执行完了过后LR等于下一条指令的地址 运行…...
python 桌面软件开发-matplotlib画图鼠标缩放拖动
继上一篇在 Java 中缩放拖动图片后,在python matplotlib中也来实现一个自由缩放拖动的例子: python matplotlib 中缩放,较为简单,只需要通过设置要显示的 x y坐标的显示范围即可。基于此,实现一个鼠标监听回调…...
【JavaScript基础】JavaScript头等函数的理解
彻底理解JavaScript头等函数 一、函数的理解 🔥 什么是函数? 一般来说,一个函数是可以通过外部代码 调用 的一个“子程序”(或在递归的情况下由内部函数调用)。像程序本身一样,一个函数由称为函数体的一…...
如何把项目上传到Gitee(详细教程)
找到项目根目录右键打开Git Bash Here 输入命令:git init 回车 输入命令:git status 输入命令:git add . 输入命令:git status git commit -m 项目描述 在Gitee官网注册好账号后,git 新建项目 填写补充git项目信息及…...
Ubuntu挂载windows下的共享文件夹
Ubuntu挂载windows下的共享文件夹 更新apt源 如果出现安装失败,需要更新apt源为阿里云 # 备份原始文件 sudo cp /etc/apt/sources.list.d/* /etc/apt/sources.list.d.bak/# 修改文件内容 sudo vim /etc/apt/sources.list# 替换内容为如下 deb https://mirrors.al…...
什么是WMS系统条码化管理
WMS系统是一种用于仓库管理的信息化系统,旨在提高仓库操作的效率和准确性。而在WMS系统中,条码化管理是一项关键的技术和方法,它通过将商品和物料打上条码,并利用扫描设备进行数据采集和处理,实现了仓库管理的全面自动…...
【云原生之kubernetes实战】在k8s环境下部署moredoc文库系统
【云原生之kubernetes实战】在k8s环境下部署moredoc文库系统 一、moredoc介绍1.1 moredoc简介1.2 moredoc技术栈二、本次实践介绍2.1 本次实践简介2.2 本次环境规划三、检查k8s环境3.1 检查工作节点状态3.2 检查系统pod状态四、创建mysql的secret资源4.1 创建部署目录4.2 创建密…...
[Database] MySQL 8.x Window / Partition Function (窗口/分区函数)
🧲相关文章 [1] MySQL 系统表解析以及各项指标查询 [2] MySQL 5.7 JSON 字段的使用的处理 [3] MySQL经典练习50题 简介 MySQL 8.0版本开始支持窗口函数 官方文档 在之前的版本中已存在的大部分聚合函数,在MySQL 8 中也可以作为窗口函数来使用 方法 / …...
openGauss Meetup(天津站)精彩回顾 | openGauss天津用户组正式成立
由openGauss社区、天开发展集团、天津市软件行业协会、天大智图(天津)科技有限公司联合主办的“openGauss Meetup • 天津站”已于10月13日落下帷幕,此次活动邀请到众多业内技术专家,从技术创新、学术创新、发展创新、以及生态共建…...
linux vim 删除多行
使用linux服务器,免不了和vi编辑打交道,命令行下删除数量少还好,如果删除很多,光靠删除键一点点删除真的是头痛,还好Vi有快捷的命令可以删除多行、范围。 删除行 在Vim中删除一行的命令是dd。 以下是删除行的分步说明…...
低概率Bug,研发敷衍说复现不到
测试工作中,经常会遇到一些低概率出现的问题,如果再是个严重问题,那测试人员的压力无疑是很大的,一方面是因为低概率难以复现,另一面则是来自项目组的压力。 如何在测试时减少此类问题的重复投入,我的思考如…...
Web前端免费接入Microsoft Azure AI文本翻译,享每月2百万个字符的翻译
Azure 文本翻译是 Azure AI 翻译服务的一项基于云的 REST API 功能。 文本翻译 API 支持实时快速准确地进行源到目标文本翻译。 文本翻译软件开发工具包 (SDK) 是一组库和工具,可用于轻松地将文本翻译 REST API 功能集成到应用程序中。 文本翻译 SDK 可跨 C#/.NET、…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
让AI看见世界:MCP协议与服务器的工作原理
让AI看见世界:MCP协议与服务器的工作原理 MCP(Model Context Protocol)是一种创新的通信协议,旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天,MCP正成为连接AI与现实世界的重要桥梁。…...
Selenium常用函数介绍
目录 一,元素定位 1.1 cssSeector 1.2 xpath 二,操作测试对象 三,窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四,弹窗 五,等待 六,导航 七,文件上传 …...
腾讯云V3签名
想要接入腾讯云的Api,必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口,但总是卡在签名这一步,最后放弃选择SDK,这次终于自己代码实现。 可能腾讯云翻新了接口文档,现在阅读起来,清晰了很多&…...
毫米波雷达基础理论(3D+4D)
3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文: 一文入门汽车毫米波雷达基本原理 :https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...
苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会
在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...
libfmt: 现代C++的格式化工具库介绍与酷炫功能
libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库,提供了高效、安全的文本格式化功能,是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全:…...
Linux中《基础IO》详细介绍
目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改,实现简单cat命令 输出信息到显示器,你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...
VisualXML全新升级 | 新增数据库编辑功能
VisualXML是一个功能强大的网络总线设计工具,专注于简化汽车电子系统中复杂的网络数据设计操作。它支持多种主流总线网络格式的数据编辑(如DBC、LDF、ARXML、HEX等),并能够基于Excel表格的方式生成和转换多种数据库文件。由此&…...
Python实现简单音频数据压缩与解压算法
Python实现简单音频数据压缩与解压算法 引言 在音频数据处理中,压缩算法是降低存储成本和传输效率的关键技术。Python作为一门灵活且功能强大的编程语言,提供了丰富的库和工具来实现音频数据的压缩与解压。本文将通过一个简单的音频数据压缩与解压算法…...
