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

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...

【安全篇】金刚不坏之身:整合 Spring Security + JWT 实现无状态认证与授权

摘要 本文是《Spring Boot 实战派》系列的第四篇。我们将直面所有 Web 应用都无法回避的核心问题&#xff1a;安全。文章将详细阐述认证&#xff08;Authentication) 与授权&#xff08;Authorization的核心概念&#xff0c;对比传统 Session-Cookie 与现代 JWT&#xff08;JS…...