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

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...