当前位置: 首页 > 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; …...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

排序算法总结(C++)

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

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

华为OD机考-机房布局

import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...