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

[算法]归并排序

参考:《漫画算法-小灰的算法之旅》

目录

参考:《漫画算法-小灰的算法之旅》

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”,浮点型,私有&#xff0…...

ES的restful风格的HTTP方法详解

ES的restful风格的HTTP方法详解 一、概述 ​ restful是一种设计风格,用于构建Web服务和API。 ​ 在restful风格中,HTTP请求方法(如GET、POST、PUT、DELETE)和URL(统一资源定位符)被用来定义服务端资源的…...

第十三章 opengl之模型(导入3D模型)

OpenGL模型导入3D模型优化使用3D模型模型 使用Assimp并创建实际的加载和转换代码。Model类结构如下&#xff1a; class Model {public:/* 函数 */Model(char *path){loadModel(path);}void Draw(Shader shader); private:/* 模型数据 */vector<Mesh> meshes;st…...

html标签表示!

html是什么&#xff1f;HTML全称为超文本标记语言&#xff0c;是一种标记语言。包括一系列标签&#xff0c;通过这些标签可以将网络上的文档格式统一&#xff0c;使分散的Internet资源连接为一个逻辑整体。HTML文本是由HTML命令组成的描述性文本&#xff0c;HTML命令可以说明文…...

前端优化,webpack打包删除无用文件,并附上批量删除文件脚本!非常好用

前言 大家可能在webpack打包项目过程中&#xff0c;常遇见一些无用的图片&#xff0c;js文件&#xff0c;怎样能够自动检测哪些是无用的文件呢&#xff1f;本文中介绍使用插件useless-files-webpack-plugin查找无用文件&#xff0c;在terminal中删除&#xff0c;附加bat批量删…...

SpringCloud之 LoadBalancer负载均衡

文章目录LoadBalancer 负载均衡一、LoadBalanced 负载均衡&#x1f33d;①观察负载均衡现象&#x1f33d;②LoadBalanced 源码剖析二、自定义负载均衡三、OpenFeign 实现负载均衡&#x1f346;①添加依赖&#x1f346;②启动类添加 EnableFeignClients&#x1f346;③创建客户端…...

idm如何下载种子文件和磁力链接 idm如何下载torrent

采用分段式下载技术并支持断点续传的idm下载加速器&#xff0c;几乎可以胜任所有的下载任务。由于该软件强大的下载能力和仅为10MB的小巧体积&#xff0c;idm被来自全球的用户亲切地称为天花板级的下载软件。那么有关idm如何下载种子文件和磁力链接&#xff0c;idm如何下载torr…...

UE4 安卓AR 识别图片

UE4 安卓AR 识别图片 开启一个插件 准备一个只有玩家出生点的场景&#xff0c;这个场景用来做识别图片的 新建一个游戏模式&#xff0c;设置好默认的pawn类&#xff1a; 一个摄像机就行了&#xff0c;代表手机开启AR会话后的那个相机 然后gamemode 事件开始运行&#xff0…...

数字化服务环境下高校成人教育图书馆服务工作的发展方向

1.利用高校成人教育图书馆的整体化优势进行图书馆网络的优化组织与协调&#xff0c;使数字化信息服务功能在图书馆数字化服务中得以充分实现&#xff0c;促使数字电子信息资源成为图书馆信息服务的有机组成部分。2.高校成人教育应该从宏观上有计划有组织地协调高校成人教育图书…...

以创作之名致敬女性开发者

作者简介&#xff1a;一名云计算网络运维人员、每天分享网络与运维的技术与干货。 座右铭&#xff1a;低头赶路&#xff0c;敬事如仪 个人主页&#xff1a;网络豆的主页​​​​​​ 前言 在昨天的2023年3月8日&#xff0c;是咱们女性朋友的节日妇女节&#xff0c;本章将会…...

【ArcGIS学习记录03】--利用DEM数据提取河网溪流--加入大型河流数据及裁剪美化

【ArcGIS学习记录03】–利用DEM数据提取河网溪流–加入大型河流数据及裁剪美化 注&#xff1a;本文仅作为自己的学习记录以备以后复习查阅 一 添加大型河流数据 数据是我自己找的&#xff0c;如果有需要的可以私信我发&#xff1a; 二 裁剪 使用这个相交的工具可以对矢量…...

VOC2012数据集取需要的几个类别

Visual Object Classes Challenge 2012 一、VOC2012二、保留 people ,移除其他类三、画一张图片3.1 新开窗口显示3.2 在jupyter notebook 里面显示一、VOC2012 这项挑战的主要目标是从许多视觉对象中识别对象 现实场景中的对象类(即不是预先分割的对象)。是的 从根本上说,…...

主成分分析(PCA)原理

主成分分析&#xff08;PCA&#xff09;原理 在高维数据处理中&#xff0c;为了简化计算量以及储存空间&#xff0c;需要对这些高维数据进行一定程度上的降维&#xff0c;并尽量保证数据的不失真。PCA和ICA是两种常用的降维方法。 PCA&#xff1a;principal component analysi…...

Git:合并一个仓库的某个分支到另一个仓库的某个分支

ps&#xff1a;&#xff08;同名分支或不同名分支均可&#xff09; 1.操作: 当前仓库A的一个指定分支1 推给 另一个仓库B的另一个指定分支2 仓库A:repo1 分支1&#xff1a;develop1 仓库B:repo2 分支2&#xff1a;develop2 2.操作命令&#xff1a; 1、git pull # 在当前仓…...

工作记录:bi重构

2023.3.8&#xff0c;我在组内进行工作汇报。内容记录如下&#xff1a; 本次重构的特点 改动大影响后续开发 所以有必要进行工作汇报&#xff0c;让组内同事了解代码的改动与现状。 为什么要重构代码&#xff1f; 正在开发的数据报告模块包含大量 widget 功能&#xff0c;…...

java明文数据加密、脱敏方法总结

前言 在一些安全性要求比较高的项目里&#xff0c;避免不了要对敏感信息进行加解密&#xff0c;比如配置文件中的敏感信息。 第一种方法&#xff08;自定义加解密&#xff09; 加解密工具类&#xff1a; public class SecurityTools {public static final String ALGORITHM…...

4N65-ASEMI高压MOS管4N65

编辑-Z 4N65在TO-220封装里的静态漏极源导通电阻&#xff08;RDS(ON)&#xff09;为2.5Ω&#xff0c;是一款N沟道高压MOS管。4N65的最大脉冲正向电流ISM为16A&#xff0c;零栅极电压漏极电流(IDSS)为10uA&#xff0c;其工作时耐温度范围为-55~150摄氏度。4N65功耗&#xff08…...

天梯赛训练L1-018 (大笨钟)

目录 1、L1-018 大笨钟 2、 如果到帮助大家&#xff0c;希望大家一键三连&#xff01;&#xff01;&#xff01; 1、L1-018 大笨钟 分数 10 题目通道 微博上有个自称“大笨钟V”的家伙&#xff0c;每天敲钟催促码农们爱惜身体早点睡觉。不过由于笨钟自己作息也不是很规律&a…...

GCC编译器编译C/C++程序(一步完成、分步完成)

以下内容源于C语言中文网的学习与整理&#xff0c;非原创&#xff0c;如有侵权请告知删除。 参考内容 &#xff08;1&#xff09;GCC 预处理器选项_dllbl的博客-CSDN博客 &#xff08;2&#xff09;Preprocessor Options (Using the GNU Compiler Collection (GCC)) 一、编译的…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...