排序算法-堆积树排序法(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、…...
uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)
UniApp 集成腾讯云 IM 富媒体消息全攻略(地理位置/文件) 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型,核心实现方式: 标准消息类型:直接使用 SDK 内置类型(文件、图片等)自…...
【堆垛策略】设计方法
堆垛策略的设计是积木堆叠系统的核心,直接影响堆叠的稳定性、效率和容错能力。以下是分层次的堆垛策略设计方法,涵盖基础规则、优化算法和容错机制: 1. 基础堆垛规则 (1) 物理稳定性优先 重心原则: 大尺寸/重量积木在下…...
Element-Plus:popconfirm与tooltip一起使用不生效?
你们好,我是金金金。 场景 我正在使用Element-plus组件库当中的el-popconfirm和el-tooltip,产品要求是两个需要结合一起使用,也就是鼠标悬浮上去有提示文字,并且点击之后需要出现气泡确认框 代码 <el-popconfirm title"是…...
20250609在荣品的PRO-RK3566开发板的Android13下解决串口可以执行命令但是脚本执行命令异常的问题
20250609在荣品的PRO-RK3566开发板的Android13下解决串口可以执行命令但是脚本执行命令异常的问题 2025/6/9 20:54 缘起,为了跨网段推流,千辛万苦配置好了网络参数。 但是命令iptables -t filter -F tetherctrl_FORWARD可以在调试串口/DEBUG口正确执行。…...
使用python进行图像处理—图像变换(6)
图像变换是指改变图像的几何形状或空间位置的操作。常见的几何变换包括平移、旋转、缩放、剪切(shear)以及更复杂的仿射变换和透视变换。这些变换在图像配准、图像校正、创建特效等场景中非常有用。 6.1仿射变换(Affine Transformation) 仿射变换是一种…...
Vue3学习(接口,泛型,自定义类型,v-for,props)
一,前言 继续学习 二,TS接口泛型自定义类型 1.接口 TypeScript 接口(Interface)是一种定义对象形状的强大工具,它可以描述对象必须包含的属性、方法和它们的类型。接口不会被编译成 JavaScript 代码,仅…...
Asp.net Core 通过依赖注入的方式获取用户
思路:Web项目中,需要根据当前登陆的用户,查询当前用户所属的数据、添加并标识对象等。根据请求头Authorization 中token,获取Redis中存储的用户对象。 本做法需要完成 基于StackExchange.Redis 配置,参考:…...
jieba实现和用RNN实现中文分词的区别
Jieba 分词和基于 RNN 的分词在技术路线、实现机制、性能特点上有显著差异,以下是核心对比: 1. 技术路线对比 维度Jieba 分词RNN 神经网络分词范式传统 NLP(规则 统计)深度学习(端到端学习)核心依赖词典…...
【AI学习】wirelessGPT多任务无线基础模型摘要
收看了关于WirelessGPT多任务无线基础模型的演讲视频,边做一个记录。 应该说,在无线通信大模型的探索方面,有一个非常有益的尝试。 在沈学明院士带领下开展 https://www.chaspark.com/#/live/1125484184592834560...
compose 组件 ---无ui组件
在 Jetpack Compose 中,确实存在不直接参与 UI 渲染的组件,它们主要用于逻辑处理、状态管理或副作用控制。这些组件虽然没有视觉界面,但在架构中扮演重要角色。以下是常见的非 UI 组件及其用途: 1. 无 UI 的 Compose 组件分类 (…...
