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

【算法】堆排序

算法-堆排序


前置知识
  • 堆(即将更新)

思路

我们现在有一个序列,怎么对它排序?
这是一个非常经典的问题,这里我们使用一个借助数据结构的算法——堆排序解决。

这里有一个序列,要对它升序排序
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);}
}

练习
  • 洛谷【模板】排序

相关文章:

【算法】堆排序

算法-堆排序 前置知识 堆&#xff08;即将更新&#xff09; 思路 我们现在有一个序列&#xff0c;怎么对它排序&#xff1f; 这是一个非常经典的问题&#xff0c;这里我们使用一个借助数据结构的算法——堆排序解决。 这里有一个序列&#xff0c;要对它升序排序 4 7 3 6 5 …...

51单片机应用从零开始(三)

51单片机应用从零开始&#xff08;一&#xff09;-CSDN博客 51单片机应用从零开始&#xff08;二&#xff09;-CSDN博客 详解 KEIL C51 软件的使用建立工程-CSDN博客 详解 KEIL C51 软件的使用设置工程编绎与连接程序-CSDN博客 目录 1. 用单片机控制第一个灯亮 2. 认识单片…...

如何在 Nginx Proxy Manager(NPM)上部署静态网站

前言 众所周知&#xff0c;我们在之前介绍过 Nginx Proxy Manager&#xff08;以下简称 NPM) 这个反向代理的神器&#xff0c;对于一些 Docker 搭建的 Web 项目&#xff0c;NPM 能够很轻松地给他们做反向代理。 然而对于一些静态网站&#xff0c;小伙伴们可能不知道怎么用 NP…...

http的几种方法

http的几种方法在 rfc2616 中进行了定义&#xff1a; https://www.rfc-editor.org/rfc/rfc2616.html#page-51 HEAD方法&#xff1a;HEAD方法和GET方法相同&#xff0c;只不过服务端只返回头&#xff0c;不返回消息体。GET方法&#xff1a;用于获取资源POST方法&#xff1a;用于…...

var、let、const关键字的特性,以及let、const暂时性死区的作用

var、let和const都是JavaScript中的关键字&#xff0c;用于声明变量。 var关键字声明的变量是函数作用域或全局作用域的&#xff0c;它在整个函数或全局范围内都是可用的。var没有块级作用域。 let关键字声明的变量是块级作用域的&#xff0c;它只在包含它的代码块中可用。le…...

IDEA 高分辨率卡顿优化

VM设置优化 -Dsun.java2d.uiScale.enabledfalse 增加该条设置&#xff0c;关闭高分切换 https://intellij-support.jetbrains.com/hc/en-us/articles/115001260010-Troubleshooting-IDE-scaling-DPI-issues-on-Windows​intellij-support.jetbrains.com/hc/en-us/articles/1…...

【AIGC】一起学习prompt提示词(4/4)【经典】【15种提示词技巧】

写的时候并没有设计好&#xff0c;要做多少期&#xff0c;还是有始有终的比较好&#xff0c;为了方便阅读&#xff0c;我把之前的3期&#xff0c;改下名字&#xff0c;放到这里。 【AIGC】一起学习prompt提示词&#xff08;1/4&#xff09; 内容摘要&#xff1a;提示词是什么…...

Linux实战一天一个小指令--《文件管理/文件查找》

阿丹&#xff1a; 作为一个java程序员进行实战开发不接触linux操作系统基本上是不可能的&#xff0c;所以这个专题就出现了&#xff0c;本文章重点解决大家关于文件管理以及文件查找查看的疑惑。我将采用语法基础用法并在下面进行高级语法的总结使用&#xff0c;方便大家学习和…...

CocosCreator3.8神秘面纱 CocosCreator 项目结构说明及编辑器的简单使用

我们通过Dashboard 创建一个2d项目&#xff0c;来演示CocosCreator 的项目结构。 等待创建完成后&#xff0c;会得到以下项目工程&#xff1a; 一、assets文件夹 assets文件夹&#xff1a;为资源目录&#xff0c;用来存储所有的本地资源&#xff0c;如各种图片&#xff0c;脚本…...

JJJ:python学习笔记

p4 没有编译的过程 源码和输入得到输出 静态语言&#xff1a;编译型 脚本语言&#xff1a;解释型 p5 又叫做胶水语言 p7 p8 p10...

SpringSecurity6从入门到上天系列第七篇:讲明白SpringBoot的自动装配完善上篇文章中的结论

文章目录 一&#xff1a;SpringBoot的自动装配 1&#xff1a;从run方法到入口类内容被注册到注解解读器中。 2&#xff1a;解析入口类注解到加载Bean实例 大神链接&#xff1a;作者有幸结识技术大神孙哥为好友&#xff0c;获益匪浅。现在把孙哥视频分享给大家。 孙哥链接&am…...

ClickHouse 原理解析之基础知识总结

ClickHouse 基础知识整理 参考ClickHouse 官方文档:https://clickhouse.com/docs/en/intro 一:行式存储和列式存储 1.行式存储和列式存储的区别 1.1 概念说明 行式存储:指存储结构化数据时,在底层的存储介质上,数据是以行的方式来组织的,即存储完一条记录的所有字段,再…...

最小花费——最短路

在 n 个人中&#xff0c;某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费&#xff0c;请问 A 最少需要多少钱使得转账后 B 收到 100 元。 输入格式 第一行输入两个正整数 n,m&#xff0c;分别表…...

Spark DataFrame join后移除重复的列

在Spark&#xff0c;两个DataFrame做join操作后&#xff0c;会出现重复的列。例如&#xff1a; Dataset<Row> moviesWithRating moviesDF.join(averageRatingMoviesDF,moviesDF.col("movieId").equalTo(averageRatingMoviesDF.col("movieId")));其s…...

NextJS工程部署到阿里云linux Ecs

nextjs项目有多种部署方式&#xff0c;本文介绍最简单的一种方式&#xff0c;将源码上传到云服务器&#xff0c;编译后使用pm2后台运行nextjs工程。 检查node、npm是否安装 查看npm版本&#xff0c;如果版本较低先升级npm版本 npm -v卸载 yum remove nodejs npm -y安装新版…...

汽车以太网IOP测试新利器

IOP测试目的 汽车以太网物理层IOP&#xff08;Interoperability &#xff09;测试&#xff0c;即测试被测对象以太网物理层之间的互操作性。用于验证车载以太网PHY能否在有限时间内建立稳定的链路&#xff1b;此外&#xff0c;还用于验证车载以太网PHY可靠性相关的诊断特性&am…...

高防IP是什么?如何隐藏源站IP?如何进行防护?

高防IP是针对互联网服务器遭受大流量的DDoS攻击后导致服务不可用的情况下,推出的付费增值服务。用户在数据不转移的情况下,就可以通过配置高防IP , 将攻击流量引流到高防|P,确保源站的稳定可靠。高防IP采用的技术手段包括DDoS防护、WAF ( Web应用程序防火墙)等,它能够有效抵御来…...

ElasticSearch---查询es集群状态、分片、索引

查看es集群状态&#xff1a; curl -XGET http://localhost:9200/_cat/health?v如果?后面加上pretty&#xff0c;能让返回的json格式化。 加上?v的返回结果&#xff0c;如下&#xff1a; epoch timestamp cluster status node.total node.data shards pri rel…...

Angular 使用教程——基本语法和双向数据绑定

Angular 是一个应用设计框架与开发平台&#xff0c;旨在创建高效而精致的单页面应用 Angular 是一个基于 TypeScript 构建的开发平台。它包括&#xff1a;一个基于组件的框架&#xff0c;用于构建可伸缩的 Web 应用&#xff0c;一组完美集成的库&#xff0c;涵盖各种功能&…...

【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 是一个平台&#xff0c;包括 .NET Framework、.NET Core、ASP.NET、C#等&#xff0c;可以构建桌面、W…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制

目录 节点的功能承载层&#xff08;GATT/Adv&#xff09;局限性&#xff1a; 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能&#xff0c;如 Configuration …...

windows系统MySQL安装文档

概览&#xff1a;本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容&#xff0c;为学习者提供全面的操作指导。关键要点包括&#xff1a; 解压 &#xff1a;下载完成后解压压缩包&#xff0c;得到MySQL 8.…...

五子棋测试用例

一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏&#xff0c;有着深厚的文化底蕴。通过将五子棋制作成网页游戏&#xff0c;可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家&#xff0c;都可以通过网页五子棋感受到东方棋类…...