[算法]归并排序
参考:《漫画算法-小灰的算法之旅》
目录
参考:《漫画算法-小灰的算法之旅》
1、什么是归并排序
2、归并的具体操作
3、代码
4、时间复杂度和空间复杂度
5、归并排序是稳定排序
1、什么是归并排序
归并排序就像是组织一场元素之间的“比武大会”,这场比武大会 分成两个阶段:
(1)分组
假设集合一共有n个元素,算法将会对集合进行逐层的对半分组。
第1层分成2个大组,每组n/2个元素;
第2层分成4个小组,每组n/4个元素;
第3层分成8个更小的组,每组n/8个元素;
……
一直到每组只有一个元素。
(2)归并
归并排序需要确定每一个元素的排列位置。当每个小组内部比较出先后顺序以后,小组之间会展开进一 步的比较和排序,合并成一个大组;大组之间继续比较和排序,再合并成更大的组.......最终,所有元素合并成了一个有序的集合。如下图所示:

2、归并的具体操作
归并操作一般需要三个步骤,我们以两个长度为4的集合为例:

第1步:创建一个额外的大集合,用于存储归并结果,长度是两个小集合之和。(p1,p2,p是三个辅助指针,用于记录当前操作的位 置。)

第2步:从左到右逐一比较两个小集合中的元素,把较小的元素优 先放入大集合。

第3步:从另一个还有剩余元素的集合中,把剩余元素按顺序复制 到大集合尾部。

3、代码


4、时间复杂度和空间复杂度
归并排序把集合一层一层进行折半分组。如果集合长度是n,那么 折半的层数就是logn,每一层进行归并操作的运算量是n。所以,归并排序的时间复杂度等于每一层的运算量×层级数,即 O(nlogn)。每次归并所创建的额外集合都会随着方法的结束而释放, 因此这部分空间不应该累加计算。由于单次归并操作开辟的最大空间 是n,所以归并排序的空间复杂度是O(n)。
5、归并排序是稳定排序
相关文章:
[算法]归并排序
参考:《漫画算法-小灰的算法之旅》 目录 参考:《漫画算法-小灰的算法之旅》 1、什么是归并排序 2、归并的具体操作 3、代码 4、时间复杂度和空间复杂度 5、归并排序是稳定排序 1、什么是归并排序 归并排序就像是组织一场元素之间的“比武大会”&…...
【UE4 RTS游戏】05-自定义日期和时间
效果步骤打开项目设置,重新设置玩家状态类为“MyGameState”打开“MyGameState”,点击类设置,选中父类为“GameStateBase”接着创建一些变量:(1)“TimeUnit”,浮点型,私有࿰…...
ES的restful风格的HTTP方法详解
ES的restful风格的HTTP方法详解 一、概述 restful是一种设计风格,用于构建Web服务和API。 在restful风格中,HTTP请求方法(如GET、POST、PUT、DELETE)和URL(统一资源定位符)被用来定义服务端资源的…...
第十三章 opengl之模型(导入3D模型)
OpenGL模型导入3D模型优化使用3D模型模型 使用Assimp并创建实际的加载和转换代码。Model类结构如下: class Model {public:/* 函数 */Model(char *path){loadModel(path);}void Draw(Shader shader); private:/* 模型数据 */vector<Mesh> meshes;st…...
html标签表示!
html是什么?HTML全称为超文本标记语言,是一种标记语言。包括一系列标签,通过这些标签可以将网络上的文档格式统一,使分散的Internet资源连接为一个逻辑整体。HTML文本是由HTML命令组成的描述性文本,HTML命令可以说明文…...
前端优化,webpack打包删除无用文件,并附上批量删除文件脚本!非常好用
前言 大家可能在webpack打包项目过程中,常遇见一些无用的图片,js文件,怎样能够自动检测哪些是无用的文件呢?本文中介绍使用插件useless-files-webpack-plugin查找无用文件,在terminal中删除,附加bat批量删…...
SpringCloud之 LoadBalancer负载均衡
文章目录LoadBalancer 负载均衡一、LoadBalanced 负载均衡🌽①观察负载均衡现象🌽②LoadBalanced 源码剖析二、自定义负载均衡三、OpenFeign 实现负载均衡🍆①添加依赖🍆②启动类添加 EnableFeignClients🍆③创建客户端…...
idm如何下载种子文件和磁力链接 idm如何下载torrent
采用分段式下载技术并支持断点续传的idm下载加速器,几乎可以胜任所有的下载任务。由于该软件强大的下载能力和仅为10MB的小巧体积,idm被来自全球的用户亲切地称为天花板级的下载软件。那么有关idm如何下载种子文件和磁力链接,idm如何下载torr…...
UE4 安卓AR 识别图片
UE4 安卓AR 识别图片 开启一个插件 准备一个只有玩家出生点的场景,这个场景用来做识别图片的 新建一个游戏模式,设置好默认的pawn类: 一个摄像机就行了,代表手机开启AR会话后的那个相机 然后gamemode 事件开始运行࿰…...
数字化服务环境下高校成人教育图书馆服务工作的发展方向
1.利用高校成人教育图书馆的整体化优势进行图书馆网络的优化组织与协调,使数字化信息服务功能在图书馆数字化服务中得以充分实现,促使数字电子信息资源成为图书馆信息服务的有机组成部分。2.高校成人教育应该从宏观上有计划有组织地协调高校成人教育图书…...
以创作之名致敬女性开发者
作者简介:一名云计算网络运维人员、每天分享网络与运维的技术与干货。 座右铭:低头赶路,敬事如仪 个人主页:网络豆的主页 前言 在昨天的2023年3月8日,是咱们女性朋友的节日妇女节,本章将会…...
【ArcGIS学习记录03】--利用DEM数据提取河网溪流--加入大型河流数据及裁剪美化
【ArcGIS学习记录03】–利用DEM数据提取河网溪流–加入大型河流数据及裁剪美化 注:本文仅作为自己的学习记录以备以后复习查阅 一 添加大型河流数据 数据是我自己找的,如果有需要的可以私信我发: 二 裁剪 使用这个相交的工具可以对矢量…...
VOC2012数据集取需要的几个类别
Visual Object Classes Challenge 2012 一、VOC2012二、保留 people ,移除其他类三、画一张图片3.1 新开窗口显示3.2 在jupyter notebook 里面显示一、VOC2012 这项挑战的主要目标是从许多视觉对象中识别对象 现实场景中的对象类(即不是预先分割的对象)。是的 从根本上说,…...
主成分分析(PCA)原理
主成分分析(PCA)原理 在高维数据处理中,为了简化计算量以及储存空间,需要对这些高维数据进行一定程度上的降维,并尽量保证数据的不失真。PCA和ICA是两种常用的降维方法。 PCA:principal component analysi…...
Git:合并一个仓库的某个分支到另一个仓库的某个分支
ps:(同名分支或不同名分支均可) 1.操作: 当前仓库A的一个指定分支1 推给 另一个仓库B的另一个指定分支2 仓库A:repo1 分支1:develop1 仓库B:repo2 分支2:develop2 2.操作命令: 1、git pull # 在当前仓…...
工作记录:bi重构
2023.3.8,我在组内进行工作汇报。内容记录如下: 本次重构的特点 改动大影响后续开发 所以有必要进行工作汇报,让组内同事了解代码的改动与现状。 为什么要重构代码? 正在开发的数据报告模块包含大量 widget 功能,…...
java明文数据加密、脱敏方法总结
前言 在一些安全性要求比较高的项目里,避免不了要对敏感信息进行加解密,比如配置文件中的敏感信息。 第一种方法(自定义加解密) 加解密工具类: public class SecurityTools {public static final String ALGORITHM…...
4N65-ASEMI高压MOS管4N65
编辑-Z 4N65在TO-220封装里的静态漏极源导通电阻(RDS(ON))为2.5Ω,是一款N沟道高压MOS管。4N65的最大脉冲正向电流ISM为16A,零栅极电压漏极电流(IDSS)为10uA,其工作时耐温度范围为-55~150摄氏度。4N65功耗(…...
天梯赛训练L1-018 (大笨钟)
目录 1、L1-018 大笨钟 2、 如果到帮助大家,希望大家一键三连!!! 1、L1-018 大笨钟 分数 10 题目通道 微博上有个自称“大笨钟V”的家伙,每天敲钟催促码农们爱惜身体早点睡觉。不过由于笨钟自己作息也不是很规律&a…...
GCC编译器编译C/C++程序(一步完成、分步完成)
以下内容源于C语言中文网的学习与整理,非原创,如有侵权请告知删除。 参考内容 (1)GCC 预处理器选项_dllbl的博客-CSDN博客 (2)Preprocessor Options (Using the GNU Compiler Collection (GCC)) 一、编译的…...
解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...
P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...
初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
