【算法】堆排序
算法-堆排序
前置知识
- 堆(即将更新)
思路
我们现在有一个序列,怎么对它排序?
这是一个非常经典的问题,这里我们使用一个借助数据结构的算法——堆排序解决。
这里有一个序列,要对它升序排序
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…...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
C++初阶-list的底层
目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
CMake基础:构建流程详解
目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
CentOS下的分布式内存计算Spark环境部署
一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架,相比 MapReduce 具有以下核心优势: 内存计算:数据可常驻内存,迭代计算性能提升 10-100 倍(文档段落:3-79…...
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.
ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #:…...
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分: 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...
