【算法】堆排序
算法-堆排序
前置知识
- 堆(即将更新)
思路
我们现在有一个序列,怎么对它排序?
这是一个非常经典的问题,这里我们使用一个借助数据结构的算法——堆排序解决。
这里有一个序列,要对它升序排序
4 7 3 6 5 1 2 8 \begin{array}{cc} 4&7&3&6&5&1&2&8 \end{array} 47365128
构建一个堆:

将堆顶放入序列,删除堆顶

重复该操作






直至堆为空。
获得的序列为:
1 2 3 4 5 6 7 8 \begin{array}{cc} 1&2&3&4&5&6&7&8 \end{array} 12345678
算法参数
- 平均时间复杂度: Θ ( n log n ) \Theta(n\log n) Θ(nlogn)
- 最好时间复杂度: O ( n log n ) O(n\log n) O(nlogn)
- 最坏时间复杂度: O ( n log n ) O(n\log n) O(nlogn)
- 空间复杂度: Θ ( n ) \Theta(n) Θ(n)
- 稳定性:不稳定
实现代码
- 手写堆版本
void heapify(int a[],int n,int i){//维护堆的性质int largest=i,l=2*i+1,r=2*i+2;if (l<n&&a[l]>a[largest])largest=l;if (r<n&&a[r]>a[largest])largest=r;if (largest!=i){swap(a[i],a[largest]);heapify(a,n,largest);}
}
void HeapSort(int a[],int n){//堆排序for (int i=n/2-1;i>=0;i--)heapify(a,n,i);for (int i=n-1;i>0;i--){swap(a[0],a[i]);heapify(a,i,0);}
}
练习
- 洛谷【模板】排序
相关文章:
【算法】堆排序
算法-堆排序 前置知识 堆(即将更新) 思路 我们现在有一个序列,怎么对它排序? 这是一个非常经典的问题,这里我们使用一个借助数据结构的算法——堆排序解决。 这里有一个序列,要对它升序排序 4 7 3 6 5 …...
51单片机应用从零开始(三)
51单片机应用从零开始(一)-CSDN博客 51单片机应用从零开始(二)-CSDN博客 详解 KEIL C51 软件的使用建立工程-CSDN博客 详解 KEIL C51 软件的使用设置工程编绎与连接程序-CSDN博客 目录 1. 用单片机控制第一个灯亮 2. 认识单片…...
如何在 Nginx Proxy Manager(NPM)上部署静态网站
前言 众所周知,我们在之前介绍过 Nginx Proxy Manager(以下简称 NPM) 这个反向代理的神器,对于一些 Docker 搭建的 Web 项目,NPM 能够很轻松地给他们做反向代理。 然而对于一些静态网站,小伙伴们可能不知道怎么用 NP…...
http的几种方法
http的几种方法在 rfc2616 中进行了定义: https://www.rfc-editor.org/rfc/rfc2616.html#page-51 HEAD方法:HEAD方法和GET方法相同,只不过服务端只返回头,不返回消息体。GET方法:用于获取资源POST方法:用于…...
var、let、const关键字的特性,以及let、const暂时性死区的作用
var、let和const都是JavaScript中的关键字,用于声明变量。 var关键字声明的变量是函数作用域或全局作用域的,它在整个函数或全局范围内都是可用的。var没有块级作用域。 let关键字声明的变量是块级作用域的,它只在包含它的代码块中可用。le…...
IDEA 高分辨率卡顿优化
VM设置优化 -Dsun.java2d.uiScale.enabledfalse 增加该条设置,关闭高分切换 https://intellij-support.jetbrains.com/hc/en-us/articles/115001260010-Troubleshooting-IDE-scaling-DPI-issues-on-Windowsintellij-support.jetbrains.com/hc/en-us/articles/1…...
【AIGC】一起学习prompt提示词(4/4)【经典】【15种提示词技巧】
写的时候并没有设计好,要做多少期,还是有始有终的比较好,为了方便阅读,我把之前的3期,改下名字,放到这里。 【AIGC】一起学习prompt提示词(1/4) 内容摘要:提示词是什么…...
Linux实战一天一个小指令--《文件管理/文件查找》
阿丹: 作为一个java程序员进行实战开发不接触linux操作系统基本上是不可能的,所以这个专题就出现了,本文章重点解决大家关于文件管理以及文件查找查看的疑惑。我将采用语法基础用法并在下面进行高级语法的总结使用,方便大家学习和…...
CocosCreator3.8神秘面纱 CocosCreator 项目结构说明及编辑器的简单使用
我们通过Dashboard 创建一个2d项目,来演示CocosCreator 的项目结构。 等待创建完成后,会得到以下项目工程: 一、assets文件夹 assets文件夹:为资源目录,用来存储所有的本地资源,如各种图片,脚本…...
JJJ:python学习笔记
p4 没有编译的过程 源码和输入得到输出 静态语言:编译型 脚本语言:解释型 p5 又叫做胶水语言 p7 p8 p10...
SpringSecurity6从入门到上天系列第七篇:讲明白SpringBoot的自动装配完善上篇文章中的结论
文章目录 一:SpringBoot的自动装配 1:从run方法到入口类内容被注册到注解解读器中。 2:解析入口类注解到加载Bean实例 大神链接:作者有幸结识技术大神孙哥为好友,获益匪浅。现在把孙哥视频分享给大家。 孙哥链接&am…...
ClickHouse 原理解析之基础知识总结
ClickHouse 基础知识整理 参考ClickHouse 官方文档:https://clickhouse.com/docs/en/intro 一:行式存储和列式存储 1.行式存储和列式存储的区别 1.1 概念说明 行式存储:指存储结构化数据时,在底层的存储介质上,数据是以行的方式来组织的,即存储完一条记录的所有字段,再…...
最小花费——最短路
在 n 个人中,某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费,请问 A 最少需要多少钱使得转账后 B 收到 100 元。 输入格式 第一行输入两个正整数 n,m,分别表…...
Spark DataFrame join后移除重复的列
在Spark,两个DataFrame做join操作后,会出现重复的列。例如: Dataset<Row> moviesWithRating moviesDF.join(averageRatingMoviesDF,moviesDF.col("movieId").equalTo(averageRatingMoviesDF.col("movieId")));其s…...
NextJS工程部署到阿里云linux Ecs
nextjs项目有多种部署方式,本文介绍最简单的一种方式,将源码上传到云服务器,编译后使用pm2后台运行nextjs工程。 检查node、npm是否安装 查看npm版本,如果版本较低先升级npm版本 npm -v卸载 yum remove nodejs npm -y安装新版…...
汽车以太网IOP测试新利器
IOP测试目的 汽车以太网物理层IOP(Interoperability )测试,即测试被测对象以太网物理层之间的互操作性。用于验证车载以太网PHY能否在有限时间内建立稳定的链路;此外,还用于验证车载以太网PHY可靠性相关的诊断特性&am…...
高防IP是什么?如何隐藏源站IP?如何进行防护?
高防IP是针对互联网服务器遭受大流量的DDoS攻击后导致服务不可用的情况下,推出的付费增值服务。用户在数据不转移的情况下,就可以通过配置高防IP , 将攻击流量引流到高防|P,确保源站的稳定可靠。高防IP采用的技术手段包括DDoS防护、WAF ( Web应用程序防火墙)等,它能够有效抵御来…...
ElasticSearch---查询es集群状态、分片、索引
查看es集群状态: curl -XGET http://localhost:9200/_cat/health?v如果?后面加上pretty,能让返回的json格式化。 加上?v的返回结果,如下: epoch timestamp cluster status node.total node.data shards pri rel…...
Angular 使用教程——基本语法和双向数据绑定
Angular 是一个应用设计框架与开发平台,旨在创建高效而精致的单页面应用 Angular 是一个基于 TypeScript 构建的开发平台。它包括:一个基于组件的框架,用于构建可伸缩的 Web 应用,一组完美集成的库,涵盖各种功能&…...
【ASP.NET】Hello World
文章目录 1. 几个概念2. 搭建开发环境2.1 .NET SDK2.2 IDE & Editor 3 First Project3.1 步骤3.2 模板3.3 项目结构3.4 请求的处理流程 Reference Link 1. 几个概念 .NET 是一个平台,包括 .NET Framework、.NET Core、ASP.NET、C#等,可以构建桌面、W…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...
回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...
华为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…...
Git常用命令完全指南:从入门到精通
Git常用命令完全指南:从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...
为什么要创建 Vue 实例
核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...
Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...
