【算法】堆排序
算法-堆排序
前置知识
- 堆(即将更新)
思路
我们现在有一个序列,怎么对它排序?
这是一个非常经典的问题,这里我们使用一个借助数据结构的算法——堆排序解决。
这里有一个序列,要对它升序排序
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…...
关于 WASM:1. WASM 基础原理
一、WASM 简介 1.1 WebAssembly 是什么? WebAssembly(WASM) 是一种能在现代浏览器中高效运行的二进制指令格式,它不是传统的编程语言,而是一种 低级字节码格式,可由高级语言(如 C、C、Rust&am…...
图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
深度学习习题2
1.如果增加神经网络的宽度,精确度会增加到一个特定阈值后,便开始降低。造成这一现象的可能原因是什么? A、即使增加卷积核的数量,只有少部分的核会被用作预测 B、当卷积核数量增加时,神经网络的预测能力会降低 C、当卷…...
MySQL JOIN 表过多的优化思路
当 MySQL 查询涉及大量表 JOIN 时,性能会显著下降。以下是优化思路和简易实现方法: 一、核心优化思路 减少 JOIN 数量 数据冗余:添加必要的冗余字段(如订单表直接存储用户名)合并表:将频繁关联的小表合并成…...
c++第七天 继承与派生2
这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分:派生类构造函数与析构函数 当创建一个派生类对象时,基类成员是如何初始化的? 1.当派生类对象创建的时候,基类成员的初始化顺序 …...
C++11 constexpr和字面类型:从入门到精通
文章目录 引言一、constexpr的基本概念与使用1.1 constexpr的定义与作用1.2 constexpr变量1.3 constexpr函数1.4 constexpr在类构造函数中的应用1.5 constexpr的优势 二、字面类型的基本概念与使用2.1 字面类型的定义与作用2.2 字面类型的应用场景2.2.1 常量定义2.2.2 模板参数…...
解密鸿蒙系统的隐私护城河:从权限动态管控到生物数据加密的全链路防护
摘要 本文以健康管理应用为例,展示鸿蒙系统如何通过细粒度权限控制、动态权限授予、数据隔离和加密存储四大核心机制,实现复杂场景下的用户隐私保护。我们将通过完整的权限请求流程和敏感数据处理代码,演示鸿蒙系统如何平衡功能需求与隐私安…...
设计模式-3 行为型模式
一、观察者模式 1、定义 定义对象之间的一对多的依赖关系,这样当一个对象改变状态时,它的所有依赖项都会自动得到通知和更新。 描述复杂的流程控制 描述多个类或者对象之间怎样互相协作共同完成单个对象都无法单独度完成的任务 它涉及算法与对象间职责…...
第2篇:BLE 广播与扫描机制详解
本文是《BLE 协议从入门到专家》专栏第二篇,专注于解析 BLE 广播(Advertising)与扫描(Scanning)机制。我们将从协议层结构、广播包格式、设备发现流程、控制器行为、开发者 API、广播冲突与多设备调度等方面,全面拆解这一 BLE 最基础也是最关键的通信机制。 一、什么是 B…...
Vuex:Vue.js 应用程序的状态管理模式
什么是Vuex? Vuex 是专门为 Vue.js 应用程序开发的状态管理模式 库。它采用集中式存储管理应用的所有组件的状态,并以相应的规则保证状态以一种可预测的方式发生变化。 在大型单页应用中,当多个组件共享状态时,简单的单向数据流…...
