高级排序算法（二）：归并排序与堆排序详解
引言
在上一章中，我们探讨了高效的快速排序及其分治思想。这一次，我们将继续探索两种同样重要的排序算法：归并排序（Merge Sort） 和 堆排序（Heap Sort）。
它们与快速排序一样，都是O(n log n)时间复杂度的排序算法，但实现方式和适用场景却各有不同。归并排序在稳定性和分布式场景中表现优异，而堆排序则在内存有限的情况下表现突出。
接下来，我们将一起深入剖析这两种排序算法的原理、实现与应用。
一、归并排序（Merge Sort）
1.1 算法思想
归并排序是典型的分治法应用，采用“分而治之”的思想，递归地将数组分成两部分，分别排序后再合并。
1.2 算法过程
- 分解：将数组从中间分成两部分，直到每部分只有一个元素（显然是有序的）。
- 合并：将两个有序的子数组合并成一个有序数组。
- 递归：对每个子数组重复上述过程。
1.3 C语言实现
#include <stdio.h>
#include <stdlib.h>// 合并两个有序子数组
void merge(int arr[], int left, int mid, int right) {int n1 = mid - left + 1; // 左子数组的大小int n2 = right - mid; // 右子数组的大小// 创建临时数组int* L = (int*)malloc(n1 * sizeof(int));int* R = (int*)malloc(n2 * sizeof(int));// 复制数据到临时数组for (int i = 0; i < n1; i++) L[i] = arr[left + i];for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];// 合并临时数组到原数组int i = 0, j = 0, k = left;while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k++] = L[i++];} else {arr[k++] = R[j++];}}// 复制剩余元素while (i < n1) arr[k++] = L[i++];while (j < n2) arr[k++] = R[j++];// 释放临时数组free(L);free(R);
}// 归并排序
void mergeSort(int arr[], int left, int right) {if (left < right) {int mid = left + (right - left) / 2; // 防止溢出mergeSort(arr, left, mid); // 排序左半部分mergeSort(arr, mid + 1, right); // 排序右半部分merge(arr, left, mid, right); // 合并两部分}
}int main() {int arr[] = {38, 27, 43, 3, 9, 82, 10};int n = sizeof(arr) / sizeof(arr[0]);mergeSort(arr, 0, n - 1);printf("排序后的数组: ");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}return 0;
}1.4 时间和空间复杂度
- 时间复杂度：
- 每次分解需要
log n层。 - 每次合并需要
O(n)时间。 - 总体时间复杂度为O(n log n)。
- 每次分解需要
- 空间复杂度：
- 由于需要额外的临时数组，空间复杂度为O(n)。
1.5 优点与缺点
- 优点：
- 时间复杂度始终为O(n log n)，无最坏情况。
- 稳定排序，适用于需要保持顺序的场景。
- 缺点：
- 需要额外的存储空间，空间复杂度较高。
二、堆排序（Heap Sort）
2.1 算法思想
堆排序是基于堆数据结构的排序算法，通过构建最大堆或最小堆实现排序。
- 最大堆：堆顶（根节点）是堆中最大的元素。
- 最小堆：堆顶（根节点）是堆中最小的元素。
堆排序的过程可以分为两个步骤：
- 构建堆：将无序数组调整为一个最大堆。
- 排序：依次将堆顶元素（最大值）与最后一个元素交换，并调整堆。
2.2 C语言实现
构建堆的核心：向下调整（Heapify）
void heapify(int arr[], int n, int i) {int largest = i; // 假设当前节点是最大的int left = 2 * i + 1; // 左子节点int right = 2 * i + 2; // 右子节点// 找到子节点中更大的值if (left < n && arr[left] > arr[largest]) {largest = left;}if (right < n && arr[right] > arr[largest]) {largest = right;}// 如果最大的不是当前节点，交换并递归调整if (largest != i) {int temp = arr[i];arr[i] = arr[largest];arr[largest] = temp;heapify(arr, n, largest);}
}堆排序主函数
void heapSort(int arr[], int n) {// 构建最大堆for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 逐步取出堆顶元素进行排序for (int i = n - 1; i > 0; i--) {// 将当前堆顶元素（最大值）移到数组末尾int temp = arr[0];arr[0] = arr[i];arr[i] = temp;// 调整剩余部分，重新构建堆heapify(arr, i, 0);}
}int main() {int arr[] = {12, 11, 13, 5, 6, 7};int n = sizeof(arr) / sizeof(arr[0]);heapSort(arr, n);printf("排序后的数组: ");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}return 0;
}2.3 时间和空间复杂度
- 时间复杂度：
- 构建堆需要
O(n)时间。 - 排序过程需要
O(n log n)时间。 - 总体时间复杂度为O(n log n)。
- 构建堆需要
- 空间复杂度：
- 原地排序，无额外空间需求，空间复杂度为O(1)。
2.4 优点与缺点
- 优点：
- 时间复杂度为O(n log n)，无最坏情况。
- 不需要额外存储空间，适合内存有限的场景。
- 缺点：
- 不稳定排序。
- 实现相对复杂，调整堆时需要更多代码。
三、对比与总结
| 特性 | 归并排序 | 堆排序 |
|---|---|---|
| 时间复杂度 | O(n log n) | O(n log n) |
| 空间复杂度 | O(n) | O(1) |
| 稳定性 | 稳定 | 不稳定 |
| 适用场景 | 数据量大，且对稳定性有要求 | 内存有限，且对稳定性无要求 |
四、总结与展望
归并排序和堆排序是经典的高级排序算法，各有优缺点。归并排序因其稳定性和良好的最坏情况表现适用于广泛场景，而堆排序因其原地排序特性在内存有限的情况下更具优势。
在下一篇文章中，我们将深入探讨线性时间排序算法（如计数排序、桶排序、基数排序），感受算法在特定场景下的极致效率，敬请期待！
归并排序与堆排序不仅是经典的排序算法，也是面试中经常被问到的重点。希望通过这篇文章，你能深入理解它们的原理与实现，为掌握高级排序算法迈出扎实的一步。
有疑问或建议？欢迎评论区讨论，我们一起进步！
相关文章：
高级排序算法（二）：归并排序与堆排序详解
引言 在上一章中，我们探讨了高效的快速排序及其分治思想。这一次，我们将继续探索两种同样重要的排序算法：归并排序（Merge Sort） 和 堆排序（Heap Sort）。 它们与快速排序一样，都是O(…...
doxygen–自动生成文档工具
原文地址：doxygen–自动生成文档工具 – 无敌牛 欢迎参观我的个人博客：无敌牛 – 技术/著作/典籍/分享等 简介 doxygen是软件开发中广泛使用的文档生成工具。它可以从源代码注释中自动生成文档，解析类、函数、参数相关信息，并生…...
5G学习笔记之SNPN系列之ID和广播消息
目录 1. 概述 2. SNPN ID 3. SNPN广播消息 1. 概述 SNPN：Stand-alone Non-Public Network，独立的非公共网络，由NPN独立运营，不依赖与PLMN网络。 SNPN不支持的5GS特性： 与EPS交互 emergency services when the UE acce…...
登录授权的实现:json web token + redis + springboot
文章目录 引言I token实现思路传统JWT TOKEN认证方式改进的JWT TOKEN认证方式redis设计II java代码实现登录接口退出登录接口登录之后接口（token解析和校验）III 常见问题400引言 应用场景： 登录认证 I token实现思路 传统JWT TOKEN认证方式 RESTful API TOKEN认证方式：…...
AlexNet：开启深度学习图像识别新纪元
一、引言 在深度学习的璀璨星空中，AlexNet 无疑是一颗极为耀眼的明星。它于 2012 年横空出世，并在 ImageNet 竞赛中一举夺冠，这一历史性的突破彻底改变了计算机视觉领域的发展轨迹，让全世界深刻认识到深度卷积神经网络在图像识别任…...
鸿蒙面试-----鸿蒙组件生命周期详解
不同颜色的是必须要会的，黑色的参考一下，只写了一些用过的还有很多组件的生命周期都没写 组件的生命周期有那些？ 我了解的有、系统组件的生命周期、页面和自定义组件的生命周期、UIAbility组件的生命周期，Navigation组件生命周期…...
Meta Llama 3.3 70B：性能卓越且成本效益的新选择
Meta Llama 3.3 70B：性能卓越且成本效益的新选择 引言 在人工智能领域，大型语言模型一直是研究和应用的热点。Meta公司最近发布了其最新的Llama系列模型——Llama 3.3 70B，这是一个具有70亿参数的生成式AI模型，它在性能上与4050…...
asp.net老项目运维，出现的问题6之数据库
数据库会有很多张表，表内一般会有自增列，如果想统一管理这个自增数值，可以使用如下方法，放在一个存储过程中，想用的时候调用存储过程即可生成数据库层面的全局唯一值： create procedure [dbo].[P_getSeqID…...
WADesk 升级 Webpack5 一些技术细节认识5和4的区别在哪里
背景 升级过程中发现有很多新的知识点，虽然未来可能永远都不会再遇到，但是仍然是一次学习的好机会，可以让自己知道，打包软件的进化之路，和原来 Webpack 4 版本的差异在哪里。 移除的依赖记录 babel/register: 在 Nod…...
什么是JVM即时编译
什么是JVM即时编译 即时编译是JVM的核心功能，他让java在性能上不输于C/C JVM（Java Virtual Machine）即 Java 虚拟机，是一种用于执行 Java 字节码的虚拟计算机。它是 Java 程序的运行核心，提供了一个独立于底层操作系统…...
《经验分享 · 软考系统分析师》
📢 大家好，我是 【战神刘玉栋】，有10多年的研发经验，致力于前后端技术栈的知识沉淀和传播。 💗 🌻 CSDN入驻不久，希望大家多多支持，后续会继续提升文章质量，绝不滥竽充数…...
HC-SR04 超声波测距模块驱动总结
一、基本原理 1.1. 引脚功能 VCC电源 (需要5V直流电源)GND地Trig信号触发脉冲 (>10us TTL脉冲)Echo输出TTL电平信号, 电平持续时间与距离程正比 1.2. 电气特性 工作电压5V工作电流15mA工作频率40kHz射程范围0.02 ~ 4m (参考值,不同厂家质量可能也不一样)测量精度1mm (理…...
VMware：CentOS 7.* 连不上网络
1、修改网络适配 2、修改网卡配置参数 cd /etc/sysconfig/network-scripts/ vi ifcfg-e33# 修改 ONBOOTyes 3、重启网卡 service network restart 直接虚拟机中【ping 宿主机】，能PING通说明centOS和宿主机网络通了，只要宿主机有网，则 Ce…...
【自动驾驶】单目摄像头实现自动驾驶3D目标检测
🍑个人主页：Jupiter. 🚀 所属专栏：传知代码 欢迎大家点赞收藏评论😊 目录 概述算法介绍演示效果图像推理视频推理 核心代码算法处理过程使用方式环境搭建下载权重文件pytorch 推理（自动选择CPU或GPU&#x…...
40分钟学 Go 语言高并发：微服务架构设计
微服务架构设计 一、知识要点总览 核心模块重要性掌握程度服务拆分高深入理解DDD领域驱动设计接口设计高掌握RESTful和gRPC设计规范服务治理高理解服务注册、发现、熔断、限流等机制部署策略中掌握DockerK8s容器化部署方案 二、详细内容讲解 1. 服务拆分 服务拆分是微服务…...
【蓝桥杯最新板】蓝桥杯嵌入式液晶上实现电子时钟
这几年蓝桥杯比赛比较适合学生技能学习，考虑板子功能，提出完成的任务。 要求在液晶完成如下图效果： 主要是实现液晶显示时钟和数字时钟，具体样式可以依据实际情况微调。 实现过程： 1.需要画圆（外圆、内圆…...
Micropython 扩展C模块＜HelloWorld＞
开发环境 MCU：Pico1（无wifi版）使用固件：自编译版本开发环境：MacBook Pro Sonoma 14.5开发工具：Thonny 4.1.6开发语言：MicroPython 1.24 执行示例 在github上获取micropython，我使…...
数据分析学习Day1-使用matplotlib生成2小时每分钟的气温可视化分析图
注意：需要提前下载matplotlib包 pip install matplotlib -i https://pypi.tuna.tsinghua.edu.cn/simple import matplotlib.pyplot as plt import random# 数据准备 x list(range(121)) # 使用 list() 转换为列表 y [random.randint(15,28) for i in range(121)]…...
域渗透-域内密码喷洒
域内密码喷洒 密码喷洒配合用户枚举使用，先进行枚举再进行喷洒 为什么不爆破，而是喷洒： 规避账户锁定策略 学习怎么设置密码锁定策略： 在工具找到组策略管理，在域下的Default Domain右键点击编辑 在计算机配置>…...
5G Multi-TRP R16~R18演进历程
提升小区边缘用户的性能，在覆盖范围内提供更为均衡的服务质量，NR中引入了多TRP协作传输的方案。多TRP协作传输通过多个TRP之间进行非相干联合传输（Non Coherent-Joint Transmission，NC-JT）、重复传输／接收或…...
Android 屏幕采集并编码为H.264
前言 我们前面基于摄像机的图像采集以及编解码已经完成了，那么接下来计划后面的三篇博文分别实现Android屏幕采集实现并进行H.264编解码、MIC音频采集并编码为AAC以及AAC解码播放，希冀可以通过这六篇博文能够对Android上面的音视频编解码有一个初步的学…...
xuggle操作视频
文章目录 xuggle操作视频 xuggle操作视频 有个需求是要读取视频的宽高，找到了Xuggle和FFmpeg两种方式，FFmpeg很强大，但是我并不需要那些功能，所以使用了轻量一点的Xuggle 引入依赖 <dependency><groupId>xuggle<…...
)
Python|Pyppeteer实现自动获取eBay商品数据【进阶版】(27)
前言 本文是该专栏的第27篇，结合优质项目案例持续分享Pyppeteer的干货知识，记得关注。 在本专栏的上一篇文章中，笔者有详细介绍基于python中的pyppeteer，“根据目标关键词，来实现自动获取eBay的商品数据”。而本文，笔者将在上一篇文章《Python|Pyppeteer实现自动获取eBa…...
Android Studio新版本的一个资源id无法找到的bug解决
Android Studio新版本的一个资源id无法找到的bug解决 文章目录 Android Studio新版本的一个资源id无法找到的bug解决一、前言二、Android Studio的无法获取到资源id的bug1、一段简单的Java代码1、错误现象2、错误解决方法 三、其他1、小结2、gradle.properties文件 其他相关属性…...
CAPL如何设置或修改CANoe TCP/IP协议栈的底层配置
在CANoe中创建网络节点作为以太网主机时，可以给其配置独立的TCP/IP Stack。 配置的协议栈有一些底层配置参数可以在界面上设置或修改，比如： MTU上图中MTU显示500只是图形界面显示错误，正确值是1500。 TCP延迟确认这些参数也可以通过CAPL动态配置，甚至CAPL还可以配置很多界…...
【git】--- 通过 git 和 gitolite 管理单仓库的 SDK
在编程的艺术世界里，代码和灵感需要寻找到最佳的交融点，才能打造出令人为之惊叹的作品。而在这座秋知叶i博客的殿堂里，我们将共同追寻这种完美结合，为未来的世界留下属于我们的独特印记。【git】--- 通过 git 和 gitolite 管理单仓库的 SDK 开发环境一、安装配置 gitolite二…...
Avalonia实战实例一：使用Prism创建项目，并创建窗口
文章目录 一、安装Avalonia的项目模板二、安装Prism框架三、简单更改App.axaml为Prism基类四、创建窗口一、安装Avalonia的项目模板 这里安装的是Avalonia 11.2.1，.Net 6.0 安装完成，创建Avalonia项目。 二、安装Prism框架 打开Nuget，搜索Prism： 不要安装Prism.Core： …...
单元测试，集成测试，系统测试的区别是什么？
实际的测试工作当中，我们会从不同的角度对软件测试的活动进行分类，题主说的“单元测试，集成测试，系统测试”，是按照开发阶段进行测试活动的划分。这种划分完整的分类，其实是分为四种 “单元测试，…...
Composer在安装的过程中经常找不到刚更新的包
明明有v2.1.0版本，安装就是找不到这个版本的包。 1. Composer 官方网址：https://getcomposer.org 中文网站：https://www.phpcomposer.com 官方文档：https://docs.phpcomposer.com 2. Packagist Packagist 是 Composer的组件仓库…...
ue5 motion matching
ue5.5 gameanimationsample 先看动画蓝图 核心两个node 第一个是根据数据选择当前的pose 第二个是缓存一段历史记录，为第一个node选择的时候提供数据。 在animinstance的update方法中 每帧都更新这个函数，每帧更新trajectory的数据 看看第一个node的…...
ThinkPHP知识库文档系统源码
知识库文档系统 一款基于ThinkPHP开发的知识库文档系统，可用于企业工作流程的文档管理，结构化记录沉淀高价值信息，形成完整的知识体系，能够轻松提升知识的流转和传播效率，更好地成就组织和个人。为部门、团队或项目搭…...
如何将自己的PHP类库发布到composer仓库
将自己的 PHP 类库发布到 Composer 仓库，需要经过一系列的准备和操作步骤，以下是详细说明： 准备工作 创建类库项目：确保你的 PHP 类库项目具有清晰的目录结构，遵循 PSR-4 等 PHP 编码规范。通常，类文件应…...
vue监听点击自己和点击其他元素；el-popover通过visible控制显隐；点击其他隐藏el-popover
场景： 一般点击元素自己，显示弹框；点击页面其他元素都是关闭 特别是处理el-popover通过visible控制显隐的时候。点击其他隐藏el-popover <el-popover :visible <template><div><div style"border: 1px solid #ccc; p…...
Strawberry Fields：探索学习量子光学编程的奇妙世界
一、Strawberry Fields 简介 Strawberry Fields 是由加拿大量子计算公司Xanadu开发的全栈 Python 库，在量子计算领域中占据着重要的地位。它为设计、模拟和优化连续变量（CV）量子光学电路提供强大工具，Strawberry Fields 的强大之…...
【初阶数据结构与算法】初阶数据结构总结之顺序表、单链表、双链表、栈、队列、二叉树顺序结构堆、二叉树链式结构（附源码）
文章目录 一、顺序表二、单链表三、双链表四、栈(先进后出)五、队列六、二叉树链式结构---堆七、二叉树链式结构接口实现 在之前我们学习了大部分初阶数据结构，我们现在从特点、优缺点以及应用场景大致总结一下，放出源码，如果想要看具体分析请…...
209. 长度最小的子数组 C++
文章目录 一、题目链接二、参考代码 一、题目链接 链接: 209. 长度最小的子数组 二、参考代码 暴力思路：两个for循环，找符合条件的子序列，复杂度（O（n^2）） int minSubArrayLen(const vector&l…...
基于python的一个简单的压力测试（DDoS）脚本
DDoS测试脚本 声明：本文所涉及代码仅供学习使用，任何人利用此造成的一切后果与本人无关 源码 import requests import threading# 目标URL target_url "http://47.121.xxx.xxx/"# 发送请求的函数 def send_request():while True:try:respo…...
异步操作、Promise和axios
1.Javascript是单线程的 什么是进程，什么是线程？ 进程：进程是操作系统分配资源和调度的基本单位。它是一个程序的实例，包含了运行程序所需的代码和数据以及其它资源。 线程：线程是进程中的实际运行单位，也是…...
微信小程序开发简易教程
微信小程序文件结构详解 1. 项目配置文件 project.config.json 项目的配置文件包含项目名称、appid、编译选项等配置示例： {"description": "项目配置文件","packOptions": {"ignore": []},"setting": {&quo…...
基于 Java 实现的环形数组队列详解
1. 环形数组队列简介 队列（Queue）是一种常用的线性数据结构，具有先进先出（FIFO）的特点。在传统的线性队列中，随着出队操作，队列前端会出现空闲空间，但这些空间无法重复使用…...
opencv函数
1、二值化图 二值化图：就是将图像中的像素改成只有两种值，其操作的图像必须是灰度图。 2.1、阈值法(THRESH_BINARY) 通过设置一个阈值，将灰度图中的每一个像素值与该阈值进行比较，小于等于阈值的像素就被设置为0（黑&…...
fastadmin集成kindeditor编辑器解决段后距问题--全网唯一
背景 由于项目的需求使用fastadmin推荐的编辑器kindeditor，使用过程中发现没有段后距这个bug。查询搜索了所有的网上来源，都没有解决方案。鉴宇客户非常需要该功能，奋战几天写端代码实现了该功能。 插件实现 KindEditor.plugin(paragra…...
【Mybatis】Mybatis 魔法世界探秘：从配置起航，开启数据持久化的奇幻入门之旅
目录 1.JDBC回顾 1.1JDBC编程 2.Mybatis使用 2.1什么是Mybatis 2.2Mybatis环境配置 1.引入依赖 2.lombok的操作 2.3Mybatis编程 1.数据库创建 2.创建实体类 3.配置数据库 4.Mapper持久层编写 5.单元测试 2.4常见的问题日志 1.密码错误 2.SQL语句错误 3.数据库…...
uni-app在image上绘制点位并回显
在 Uni-app 中绘制多边形可以通过使用 Canvas API 来实现。Uni-app 是一个使用 Vue.js 开发所有前端应用的框架，同时支持编译为 H5、小程序等多个平台。由于 Canvas 是 H5 和小程序中都支持的 API，所以通过 Canvas 绘制多边形是一个比较通用的方法。 1.…...
top命令和系统负载
1 top中的字段说明 top是一个实时系统监视工具，可以动态展现出 CPU 使用率、内存使用情况、进程状态等信息，注意这些显示的文本不能直接使用 > 追加到文件中。 [rootvv~]# top -bn 1 | head top - 20:08:28 up 138 days, 10:29, 4 users, load av…...
算法之要求对任意的i，j，k三个位置，如果i ＜ j ＜ k，都有arr[i] + arr[k] != arr[j]，返回构造出的arr。
目录 1. 题目2. 解释3. 思路4. 代码 Code06_MakeNo5. 总结 1. 题目 给定一个正整数M，请构造出一个长度为M的数组arr，要求对任意的i，j，k三个位置，如果i < j < k，都有arr[i] arr[k] ! arr[j]返回构造…...
Y3编辑器文档4：触发器
文章目录 一、触发器简介1.1 触发器界面1.2 ECA语句编辑及快捷键1.3 参数设置1.4 变量设置1.5 实体触发器1.6 函数库与触发器复用 二、触发器的多层结构2.1 子触发器（在游戏内对新的事件进行注册）2.2 触发器变量作用域2.3 复合条件2.4 循环2.5 计时器2.6…...
Ubuntu中安装配置交叉编译工具并进行测试
01-下载获取交叉编译工具的源码 按照博文 https://blog.csdn.net/wenhao_ir/article/details/144325141的方法，把imx6ull的BSP下载好后，其中就有交叉编译工具。 当然，为了将来使用方便，我已经把它压缩并传到了百度网盘ÿ…...
HCIA笔记7--OSPF协议入门
文章目录 0. 路由分类1. OSPF介绍1.1 概念1.2 报文类型 2. 邻接关系的建立2.1 邻居关系的建立2.2 邻接关系的形成2.3 ospf状态机 3. DR与BDR3.1 为什么要有DR和BDR？3.2 DR和BDR的选举原则 4. ospf的配置4.1 内部优先级 5. 问题5.1 三层环路如何解决？ Ref…...
文件系统--底层架构（图文详解）
一、文件系统的底层存储与寻址 当我们谈到文件系统的底层结构时，最关键的问题是：文件的数据与元数据（属性）如何存储在磁盘上，以及系统是如何定位这些数据的？在谈及文件系统之前，我们要先对储存…...