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

11.7 堆排序

目录

11.7   堆排序

11.7.1   算法流程

11.7.2   算法特性


11.7   堆排序

Tip

阅读本节前,请确保已学完“堆“章节。

堆排序(heap sort)是一种基于堆数据结构实现的高效排序算法。我们可以利用已经学过的“建堆操作”和“元素出堆操作”实现堆排序。

  1. 输入数组并建立小顶堆,此时最小元素位于堆顶。
  2. 不断执行出堆操作,依次记录出堆元素,即可得到从小到大排序的序列。

以上方法虽然可行,但需要借助一个额外数组来保存弹出的元素,比较浪费空间。在实际中,我们通常使用一种更加优雅的实现方式。

11.7.1   算法流程

设数组的长度为 𝑛 ,堆排序的流程如图 11-12 所示。

  1. 输入数组并建立大顶堆。完成后,最大元素位于堆顶。
  2. 将堆顶元素(第一个元素)与堆底元素(最后一个元素)交换。完成交换后,堆的长度减 1 ,已排序元素数量加 1 。
  3. 从堆顶元素开始,从顶到底执行堆化操作(sift down)。完成堆化后,堆的性质得到修复。
  4. 循环执行第 2. 步和第 3. 步。循环 𝑛−1 轮后,即可完成数组排序。

Tip

实际上,元素出堆操作中也包含第 2. 步和第 3. 步,只是多了一个弹出元素的步骤。

heap_sort_step11

图 11-12   堆排序步骤

在代码实现中,我们使用了与“堆”章节相同的从顶至底堆化 sift_down() 函数。值得注意的是,由于堆的长度会随着提取最大元素而减小,因此我们需要给 sift_down() 函数添加一个长度参数 𝑛 ,用于指定堆的当前有效长度。代码如下所示:

heap_sort.c

/* 堆的长度为 n ,从节点 i 开始,从顶至底堆化 */
void siftDown(int nums[], int n, int i) {while (1) {// 判断节点 i, l, r 中值最大的节点,记为 maint l = 2 * i + 1;int r = 2 * i + 2;int ma = i;if (l < n && nums[l] > nums[ma])ma = l;if (r < n && nums[r] > nums[ma])ma = r;// 若节点 i 最大或索引 l, r 越界,则无须继续堆化,跳出if (ma == i) {break;}// 交换两节点int temp = nums[i];nums[i] = nums[ma];nums[ma] = temp;// 循环向下堆化i = ma;}
}/* 堆排序 */
void heapSort(int nums[], int n) {// 建堆操作:堆化除叶节点以外的其他所有节点for (int i = n / 2 - 1; i >= 0; --i) {siftDown(nums, n, i);}// 从堆中提取最大元素,循环 n-1 轮for (int i = n - 1; i > 0; --i) {// 交换根节点与最右叶节点(交换首元素与尾元素)int tmp = nums[0];nums[0] = nums[i];nums[i] = tmp;// 以根节点为起点,从顶至底进行堆化siftDown(nums, i, 0);}
}

11.7.2   算法特性

  • 时间复杂度为 𝑂(𝑛log⁡𝑛)、非自适应排序:建堆操作使用 𝑂(𝑛) 时间。从堆中提取最大元素的时间复杂度为 𝑂(log⁡𝑛) ,共循环 𝑛−1 轮。
  • 空间复杂度为 𝑂(1)、原地排序:几个指针变量使用 𝑂(1) 空间。元素交换和堆化操作都是在原数组上进行的。
  • 非稳定排序:在交换堆顶元素和堆底元素时,相等元素的相对位置可能发生变化。

相关文章:

11.7 堆排序

目录 11.7 堆排序 11.7.1 算法流程 11.7.2 算法特性 11.7 堆排序 Tip 阅读本节前&#xff0c;请确保已学完“堆“章节。 堆排序&#xff08;heap sort&#xff09;是一种基于堆数据结构实现的高效排序算法。我们可以利用已经学过的“建堆操作”和“元素出堆操作”…...

Patchwork++:基于点云的快速、稳健的地面分割方法

1. 背景 论文发表在2022IROS&#xff0c;是Patchwork的改进版本。算法通过数学方法进行快速而鲁棒性很强的地面分割&#xff0c;在智能机器人上的可操作性非常强。通过微调算法&#xff0c;可以应用于16-beams等多种规格的激光雷达。由于激光雷达点云数据标注的难度非常大&…...

Llama改进之——分组查询注意力

引言 今天介绍LLAMA2模型引入的关于注意力的改进——分组查询注意力(Grouped-query attention,GQA)1。 Transformer中的多头注意力在解码阶段来说是一个性能瓶颈。多查询注意力2通过共享单个key和value头&#xff0c;同时不减少query头来提升性能。多查询注意力可能导致质量下…...

英伟达开源新利器NV-Embed向量模型,基于双向注意力的LLM嵌入模型,MTEB 56项任务排名第一

前言 文本嵌入模型能够将文本信息转化为稠密的向量表示&#xff0c;并在信息检索、语义相似度计算、文本分类等众多自然语言处理任务中发挥着关键作用。近年来&#xff0c;基于解码器的大型语言模型 (LLM) 开始在通用文本嵌入任务中超越传统的 BERT 或 T5 嵌入模型&#xff0c…...

JVM之【GC-垃圾清除算法】

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集算法主要分为以下几种&#xff1a; 标记-清除算法&#xff08;Mark-Sweep&#xff09;复制算法&#xff08;Copying&#xff09;标记-整理算法&#xff08;Mark-Compact&#xff09;分代收集算法&#xff08;Generational C…...

数据分析每周挑战——心衰患者特征数据集

这是一篇关于医学数据的数据分析&#xff0c;但是这个数据集数据不是很多。 背景描述 本数据集包含了多个与心力衰竭相关的特征&#xff0c;用于分析和预测患者心力衰竭发作的风险。数据集涵盖了从40岁到95岁不等年龄的患者群体&#xff0c;提供了广泛的生理和生活方式指标&a…...

单例模式(Java实现)

我的相关文章&#xff1a; JavaSE 学习记录-CSDN博客 多线程笔记-CSDN博客 单例模式&#xff08;Java实现&#xff09;-CSDN博客 JUC笔记-CSDN博客 注解与反射&#xff08;Java&#xff0c;类加载机制&#xff0c;双亲委派机制&#xff09;-CSDN博客 1. 懒汉式线程不安全 pu…...

24.面向对象六大原则

目录介绍 00.面向对象六大原则01.代码单一职责原则02.代码开放封闭原则03.代码里氏替换原则04.代码依赖倒置原则05.代码接口隔离原则06.代码迪米特原则00.面向对象六大原则 六大原则一句话介绍 单一职责原则:指一个类的功能要单一,不能包罗万象。开放封闭原则:指一个模块在扩…...

Vue3-shallowRef与shallowReactive

shallowRef 作用&#xff1a;创建一个响应式数据&#xff0c;但只对顶层属性进行响应式处理。 用法&#xff1a; let myVar shallowRef(initialValue);特点&#xff1a;只跟踪引用值的变化&#xff0c;不关心值内部的属性变化。 shallowReactive 作用&#xff1a;创建一个浅…...

CI/CD(基于ESP-IDF)

主要参考资料 B站乐鑫信息科技《【乐鑫全球开发者大会】DevCon23 #15 &#xff5c;通过 CI/CD 进行流水线开发》 pytest-embedded乐鑫文档: https://docs.espressif.com/projects/pytest-embedded/en/latest/api.html 目录 CI/CD简介乐鑫内部CI/CD测试GitLab CI/CDGitHub Actio…...

聚观早报 | 东风奕派eπ008将上市;苹果Vision Pro发布会

聚观早报每日整理最值得关注的行业重点事件&#xff0c;帮助大家及时了解最新行业动态&#xff0c;每日读报&#xff0c;就读聚观365资讯简报。 整理丨Cutie 6月3日消息 东风奕派eπ008将上市 苹果Vision Pro发布会 特斯拉Model 3高性能版开售 小米14推送全新澎湃OS系统 …...

k8s牛客面经篇

k8s的pod版块: k8s的网络版块: k8s的deployment版块: k8s的service版块: k8s的探针板块: k8s的控制调度板块: k8s的日志监控板块: k8s的流量转发板块: k8s的宏观版块:...

第9周 基于MinIO与OSS实现分布式与云存储

第9周 基于MinIO与OSS实现分布式与云存储 1. 基于mybatis-plus数据修改非空属性忽略更新2. 文件上传3. 分布式文件存储3.1 文件存储架构演变4. Minio docker安装5. 文件服务整合minio依赖minio API测试yml配置minio信息minio配置类业务:上传文件6. 云存储阿里OSS:要钱6.1 依赖6…...

【Linux内核-编程指南】

■ IPC组件 添加链接描述 ■ ■ ■ ■ ■...

Go 编程风格指南 - 最佳实践

Go 编程风格指南 - 最佳实践 原文&#xff1a;https://google.github.io/styleguide/go 概述 | 风格指南 | 风格决策 | 最佳实践 注意&#xff1a; 本文是 Google Go 风格 系列文档的一部分。本文档是 规范性(normative) 但不是强制规范(canonical)&#xff0c;并且从属于Goo…...

awk的应用

步骤一&#xff1a;awk的基本用法 1&#xff09;基本操作方法 格式1&#xff1a;awk [选项] [条件]{指令} 文件 格式2&#xff1a;前置指令 | awk [选项] [条件]{指令} 其中&#xff0c;print 是最常用的编辑指令&#xff1b;若有多条编辑指令&#xff0c;可用分号分隔。 …...

【网络原理】HTTP|认识请求“报头“|Host|Content-Length|Content-Type|UA|Referer|Cookie

目录 认识请求"报头"(header) Host Content-Length Content-Type User-Agent(简称UA) Referer &#x1f4a1;Cookie&#xff08;最重要的一个header&#xff0c;开发&面试高频问题&#xff09; 1.Cookie是啥&#xff1f; 2.Cookie怎么存的&#xff1f; …...

深入React Hoooks:从基础到自定义 Hooks

使用 useContext useContext 是另一个常用的 Hook&#xff0c;它可让我们在函数组件中轻松访问 React 的 context。如果你的应用程序依赖于一些全局状态&#xff0c;或者你希望避免将 props 一层一层地传递到子组件&#xff0c;context 很有用。你可以在父组件设置一个值&…...

9.7 Go语言入门(映射 Map)

Go语言入门&#xff08;映射 Map&#xff09; 目录六、映射 Map1. 声明和初始化映射1.1 使用 make 函数1.2 使用映射字面量 2. 映射的基本操作2.1 插入和更新元素2.2 访问元素2.3 检查键是否存在2.4 删除元素2.5 获取映射的长度 3. 遍历映射4. 映射的注意事项4.1 映射的零值4.2…...

过期视频怎么恢复?如何从手机、电脑和其他设备中恢复?

过期视频是指那些被误删、丢失或因系统升级等原因而无法正常访问的视频文件。这些视频可能包含了我们珍贵的回忆、重要的信息或者具有商业价值的内容。过期视频的恢复可以帮助我们找回失去的数据&#xff0c;减少损失&#xff0c;提高工作效率和生活质量。过期视频怎么恢复&…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...

前端高频面试题2:浏览器/计算机网络

本专栏相关链接 前端高频面试题1&#xff1a;HTML/CSS 前端高频面试题2&#xff1a;浏览器/计算机网络 前端高频面试题3&#xff1a;JavaScript 1.什么是强缓存、协商缓存&#xff1f; 强缓存&#xff1a; 当浏览器请求资源时&#xff0c;首先检查本地缓存是否命中。如果命…...

机器学习的数学基础:线性模型

线性模型 线性模型的基本形式为&#xff1a; f ( x ) ω T x b f\left(\boldsymbol{x}\right)\boldsymbol{\omega}^\text{T}\boldsymbol{x}b f(x)ωTxb 回归问题 利用最小二乘法&#xff0c;得到 ω \boldsymbol{\omega} ω和 b b b的参数估计$ \boldsymbol{\hat{\omega}}…...