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

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...

华为OD机试-最短木板长度-二分法(A卷,100分)

此题是一个最大化最小值的典型例题&#xff0c; 因为搜索范围是有界的&#xff0c;上界最大木板长度补充的全部木料长度&#xff0c;下界最小木板长度&#xff1b; 即left0,right10^6; 我们可以设置一个候选值x(mid)&#xff0c;将木板的长度全部都补充到x&#xff0c;如果成功…...

DBLP数据库是什么?

DBLP&#xff08;Digital Bibliography & Library Project&#xff09;Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高&#xff0c;数据库文献更新速度很快&#xff0c;很好地反映了国际计算机科学学术研…...