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

堆排序--C++实现

1. 简介

堆排序利用的是堆序性,最小堆进行从大到小的排序。
先建初堆,保证堆序性。将堆顶元素与最后一个元素交换,
就将当前堆中的最大(小)的元素放到了最后后。堆大小递减,再重新调整堆选出第二大,重复上述过程。

2. 实现

2.1 建初堆

由于堆具有递归性,即以根节点的所有子树都是一个堆。

我们需要从下往上调整堆。即从完全二叉树的最大非叶子节点开始调整堆,直到根节点。

这样才能保证堆序性。

对于数组3,4,1,2,5 ,建初堆的过程。

在这里插入图片描述

  • 代码
template<typename T>
void adj_heap(std::vector<T> &arr,std::size_t rt, std::size_t bd) {T v = arr[rt];std::size_t child;std::size_t i;for (i = rt; i < bd; i = child) {child = i * 2 + 1;if ( child + 1 < bd && arr[child + 1] < arr[child])++child;if (child >= bd || v <= arr[child] ) {break;}else{arr[i] = arr[child];}}arr[i] = v;
}template<typename T>
void make_orig_heap(std::vector<T> &arr, std::size_t sz) {for (std::size_t i = sz/2 - 1; i != -1; --i){adj_heap(arr, i, sz);}
}
2.2 堆排序

建立初始堆后,我们就确定了最小(大)的元素。

将该元素与最后位置交换,并将堆大小 - 1。

我们就又得到了一个未调整的堆。我们重复调整堆和交换元素的过程,直到最后堆大小为1。

所以,最小堆进行排序形成的序列是从大到小。
过程如图
在这里插入图片描述

  • 代码
template<typename T>
void heap_sort(std::vector<T> &arr, std::size_t sz) {if ( 0 == sz)return ;make_orig_heap(arr, sz);for (std::size_t i = sz - 1; i > 0; --i) {T last = arr[i];arr[i] = arr[0];arr[0] = last;adj_heap(arr, 0, i);}}

相关文章:

堆排序--C++实现

1. 简介 堆排序利用的是堆序性&#xff0c;最小堆进行从大到小的排序。 先建初堆&#xff0c;保证堆序性。将堆顶元素与最后一个元素交换&#xff0c; 就将当前堆中的最大(小)的元素放到了最后后。堆大小递减&#xff0c;再重新调整堆选出第二大&#xff0c;重复上述过程。 2…...

【数据结构】数组和字符串(十四):字符串匹配1:朴素的模式匹配算法(StringMatching)

文章目录 4.3 字符串4.3.1 字符串的定义与存储4.3.2 字符串的基本操作4.3.3 模式匹配算法1. 算法原理2. ADL语言3. 伪代码4. C语言实现5 时间复杂度 4.3 字符串 字符串(String)是由零个或多个字符(char)顺序排列组成的有限序列&#xff0c;简称为串。例如 “good morning”就是…...

VMWare虚拟机问题

镜像下载 阿里巴巴开源镜像站-OPSX镜像站-阿里云开发者社区...

代码随想录算法训练营第23期day39 |62.不同路径、63. 不同路径 II

目录 一、&#xff08;leetcode 62&#xff09;不同路径 1.动态规划 1&#xff09;确定dp数组&#xff08;dp table&#xff09;以及下标的含义 2&#xff09;确定递推公式 3&#xff09;dp数组的初始化 4&#xff09;确定遍历顺序 5&#xff09;举例推导dp数组 2.数论方…...

白帽黑客入门,“每天一个黑客技巧”实现黑客的自我突破 !(附工具包!)

年底了&#xff0c;不少朋友都是在总结一年的学习成果。最后发现完成情况与自己最初定下的目标相去甚远。 同时也针对粉丝和网上大部分存在的问题进行了整理&#xff1a; “为什么我感觉学安全好难&#xff1f;” “渗透测试到底该怎么学&#xff1f;” “为什么总是挖不到漏…...

Jmeter参数化 —— 循环断言多方法

1、参数化接口测试数据 注意&#xff1a;csv文档参数化&#xff0c;里面有多少条数据&#xff0c;就要在线程组里循环多少次&#xff0c;不然就只执行一次 2、添加配置元件-计数器 关于计数器 ①Starting Value&#xff1a;给定计数器的初始值; ②递增&#xff1a;每次循环迭代…...

Autosar诊断实战系列26-Dem(DTCEvent)要点及配置开发详解

本文框架 前言1. Dem及其与其他模块交互介绍1.1 与DCM模块交互1.1.1 0x14服务调用时序1.1.2 0x85服务调用时序1.1.3 0x19服务调用时序1.2 与Fim模块交互1.3 与NvM模块交互1.4 与BswM模块交互1.5 与其他BSW及APP模块交互2. Dem配置开发介绍2.1 DemGeneral配置2.1.1 DemGeneral一…...

STL(第五课):queue

STL&#xff08;标准模板库&#xff09;是一种C标准库&#xff0c;在其中包含了许多常用的数据结构和算法。其中&#xff0c;queue就是STL库中的一个数据结构&#xff0c;用于实现队列&#xff08;先进先出FIFO&#xff09;。 使用STL queue&#xff0c;需要引入头文件<queu…...

点大商城V2版 2.5.2.1 全开源独立版 多小程序端+unipp安装教程

点大商城V2是一款采用全新界面设计支持多端覆盖的小程序应用&#xff0c;支持H5、微信公众号、微信小程序、头条小程序、支付宝小程序、百度小程序&#xff0c;本程序是点大商城V2独立版&#xff0c;包含全部插件&#xff0c;代码全开源&#xff0c;并且有VUE全端代码。分销&am…...

Redo Log(重做日志)的刷盘策略

1. 概述 Redo Log&#xff08;重做日志&#xff09;是 InnoDB 存储引擎中的一种关键组件&#xff0c;用于保障数据库事务的持久性和崩溃恢复。InnoDB 将事务所做的更改先记录到重做日志&#xff0c;之后再将其应用到磁盘上的数据页。 刷盘策略&#xff08;Flush Policy&#x…...

QT窗体之间值的传递,多种方法实现

目录 1. 信号和槽机制 2. 全局变量或单例模式 3. 事件过滤器 4. Qt属性系统 5. 使用QSettings类 在Qt中&#xff0c;有多种方法可以在窗体之间传递值。下面是一些常用的方法&#xff1a; 1. 信号和槽机制 使用Qt的信号和槽机制是一种常见的方式来在窗体之间传递值。您可以…...

政务服务技能竞赛中用到的软件和硬件

政务服务技能竞赛包括争上游、抢先机、秀风采、比擂台几个环节&#xff0c;用到选手端平板、评委端平板、主持人平板、抢答器等设备、抢答器等。分别计算团队分和个人分。答题规则和计分方案均较为复杂&#xff0c;一般竞赛软件无法实现&#xff0c;要用到高端竞赛软件&#xf…...

tcp/ip该来的还是得来

1. TCP/IP、Http、Socket的区别 \qquad 区别是&#xff1a;TCP/IP即传输控制/网络协议&#xff0c;也叫作网络通讯协议&#xff0c;它是在网络的使用中的最基本的通信协议。Http是一个简单的请求-响应协议&#xff0c;它通常运行在TCP之上。Socket是对网络中不同主机上的应用进…...

OpenCV官方教程中文版 —— 图像修复

OpenCV官方教程中文版 —— 图像修复 前言一、基础二、代码三、更多资源 前言 本节我们将要学习&#xff1a; • 使用修补技术去除老照片中小的噪音和划痕 • 使用 OpenCV 中与修补技术相关的函数 一、基础 在我们每个人的家中可能都会几张退化的老照片&#xff0c;有时候…...

前端难学还是后端难学?系统安全,web安全,网络安全是什么区别?

系统安全&#xff0c;web安全&#xff0c;网络安全是什么区别&#xff1f;三无纬度安全问题 系统安全&#xff0c;可以说是电脑软件的安全问题&#xff0c;比如windows经常提示修复漏洞&#xff0c;是一个安全问题 网页安全&#xff0c;网站安全&#xff0c;比如&#xff0c;…...

diffusers-Load pipelines,models,and schedulers

https://huggingface.co/docs/diffusers/using-diffusers/loadinghttps://huggingface.co/docs/diffusers/using-diffusers/loading 有一种简便的方法用于推理是至关重要的。扩散系统通常由多个组件组成&#xff0c;如parameterized model、tokenizers和schedulers&#xff0c…...

私域营销必备:轻松掌握微信CRM管理方法

大家在微信私域营销中都遇到了什么问题&#xff1f; 比如管理时间不够&#xff0c;群发实效性低&#xff0c;自动回复无法适应变化等等。 我们可以利用微信CRM这个工具&#xff0c;轻松解决这些问题。 请问你们最想用这个工具解决什么问题呢&#xff1f; 使用微信CRM不仅可…...

最长回文子串-LeetCode5 动态规划

由于基础还不是很牢固 一时间只能想到暴力的解法: 取遍每个子串 总数量nn-1n-2…1 O(n^2) 判断每个子串是否属于回文串 O(n) 故总时间复杂度为O(n^3) class Solution { public:string longestPalindrome(string s) { int max0;string ret;for(int i0;i<s.size();i)for(int…...

mysql简单备份和恢复

版本&#xff1a;mysql8.0 官方文档 &#xff1a;MySQL :: MySQL 8.0 Reference Manual :: 7 Backup and Recovery 1.物理备份恢复 物理备份是以数据文件形式备份。这种方式效率高点&#xff0c;适合大型数据库备份。物理备份可冷备可热备。 使用mysqlbackup 命令进行物理备…...

JMeter介绍

1. JMeter是什么&#xff1f; 是Apache组织开发基于Java的接口测试工具&#xff0c;性能测试工具 2.JMeter的优缺点 优点&#xff1a; 开源&#xff0c;免费 跨平台 支持多协议 轻量级别 缺点&#xff1a; 不支持IP欺骗 不可验证页面UI 3.JMeter可以用来做什么&#xff1f; …...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...