归并排序 nO(lgn)
大家好,我是蓝胖子,我一直相信编程是一门实践性的技术,其中算法也不例外,初学者可能往往对它可望而不可及,觉得很难,学了又忘,忘其实是由于没有真正搞懂算法的应用场景,所以我准备出一个系列,囊括我们在日常开发中常用的算法,并结合实际的应用场景,真正的感受算法的魅力。
代码已经上传github
https://github.com/HobbyBear/codelearning/tree/master/mergesort
算法原理
每每实现算法的时候,我总是倾向于用文字将算法的逻辑描述出来,当你能清晰的描述算法逻辑的时候,实现起来就是水到渠成的事情。
所以,我们接下来首先看下归并排序的算法逻辑。归并排序的时间复杂度是nO(lg n),它要求每次 将数组一分为二,被分割的数组又一分为二直至不能被分割,最后由底向上进行两两合并。你可以看到,假设数组长度是n,整个过程一共有lg n层,每一层需要对n个元素进行合并,所以时间复杂度是nO(lg n)。如下图所示:

合并的过程是将合并的两个有序数组的元素变成一个有序数组的过程,我们把这个过程称为merge,于是我们将 归并排序的详细步骤总结为如下的步骤,
1,将数组一分为二,形成左右子数组。
2,对左子数组进行归并排序。
3,对右子数组进行归并排序。
4,对左右子数组进行merge。
详细的merge操作我们可以在O(n)时间复杂度内完成,详细步骤可以总结如下:
1,用i表示左子数组当前遍历的元素,j表示右边子数组当前遍历的元素。
2,创建一个新数组,用于保存排好序的元素,开始遍历左右子数组,如果左右子数组都没有遍历完,则比较各自当前遍历元素的大小,将小的元素复制到新数组,然后移动小元素所在数组当前遍历的指针指向下一个遍历元素。
3,如果其中一个数组遍历完成则只需要将,没有遍历完的那个数组剩下元素全部复制到新数组即可。
实现
了解了上述详细步骤后,我们可以很容易的用递归实现上述归并排序逻辑。
// 将数组[l...r]一分为二,分别对左右数组进行排序,然后对排序好的数组进行归并
func mergesort(arr []int, l, r int) { if l >= r { return } mid := (l + r) / 2 mergesort(arr, l, mid) mergesort(arr, mid+1, r) merge(arr, l, mid, r)
}
merge 部分代码如下,
写算法逻辑的时候一定要注意边界条件,比如我这里定义的是闭区间,那么下面的逻辑都是按闭区间去写的。
// [l...mid] [mid+1...r]
func merge(arr []int, l, mid, r int) { arr1 := arr[l : mid+1] arr2 := arr[mid+1 : r+1] newArr := make([]int, r-l+1) i := 0 // 当前遍历元素 j := 0 k := 0 for i < len(arr1) && j < len(arr2) { if arr1[i] > arr2[j] { newArr[k] = arr2[j] j++ k++ continue } newArr[k] = arr1[i] k++ i++ } if i == len(arr1) { copy(newArr[k:], arr2[j:]) } if j == len(arr2) { copy(newArr[k:], arr1[i:]) } copy(arr[l:], newArr)
}
应用 求解逆序对的数量
关于归并排序的一个应用,我这里用leetcode一个题举例,这个题是leetcode 的剑指 Offer 51题,求解逆序对。
剑指 Offer 51. 数组中的逆序对
困难
1.1K
相关企业
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。 示例 1:
输入: [7,5,6,4]
输出: 5 限制: 0 <= 数组长度 <= 50000
这道题可以采用归并排序的思想,在merge时,得到逆序对的数量,如下,

merge时的两个数组是有序的,且归并排序的左右数组的相对顺序是不变的,当右边数组合并到左边数组时,如果左边的数组元素大,则说左边数组当前遍历的元素和其以后的元素都可以和右边的数组构成一个逆序对。
所以我们可以在merge的代码逻辑中添加一段累计逆序对的逻辑,如下:
func mergeCopy(arr []int, l, mid, r int, cnt *int) { arr1 := arr[l : mid+1] arr2 := arr[mid+1 : r+1] newArr := make([]int, r-l+1) i := 0 // 当前遍历元素 j := 0 k := 0 for i < len(arr1) && j < len(arr2) { if arr1[i] > arr2[j] { newArr[k] = arr2[j] // 新增cnt 变量用于保存逆序对的数量*cnt += len(arr1) - i j++ k++ continue } newArr[k] = arr1[i] k++ i++ } if i == len(arr1) { copy(newArr[k:], arr2[j:]) } if j == len(arr2) { copy(newArr[k:], arr1[i:]) } copy(arr[l:], newArr)
}
相关文章:
归并排序 nO(lgn)
大家好,我是蓝胖子,我一直相信编程是一门实践性的技术,其中算法也不例外,初学者可能往往对它可望而不可及,觉得很难,学了又忘,忘其实是由于没有真正搞懂算法的应用场景,所以我准备出…...
数据库Mysql三大引擎(InnoDB、MyISAM、 Memory)与逻辑架构
MySQL数据库及其分支版本主要的存储引擎有InnoDB、MyISAM、 Memory等。简单地理解,存储引擎就是指表的类型以及表在计算机上的存储方式。存储引擎的概念是MySQL的特色,使用的是一个可插拔存储引擎架构,能够在运行的时候动态加载或者卸载这些存…...
Python数据分析实战-实现Mann-Whitney U检验(附源码和实现效果)
实现功能 使用scipy.stats模块中的mannwhitneyu函数来实现Mann-Whitney U检验,该检验用于比较两个独立样本的分布是否有显著差异。 实现代码 from scipy.stats import mannwhitneyu# 两个独立样本的数据 group1 [1, 2, 3, 4, 5] group2 [6, 7, 8, 9, 10]# 执行…...
车载SBC芯片概论
+他V hezkz17进数字音频系统研究开发交流答疑群(课题 参考英飞凌SBC官网资料:https://www.infineon.com/cms/cn/product/automotive-system-ic/system-basis-chips-sbc/ SBC芯片在汽车电子领域可谓占一席之地了。那么什么是SBC?怎么用?用在哪里?主要特性? 1.什么是SBC?…...
【ARM AMBA5 CHI 入门 12.1 -- CHI 链路层详细介绍 】
文章目录 CHI 版本介绍1.1 CHI 链路层介绍1.1.1 Flit 切片介绍1.1.2 link layer credit(L-Credit)机制1.1.3 Channel1.1.4 Port1.1. RN Node 接口定义1.1.6 SN Node 接口定义1.2 Channel interface signals1.2.1 Request, REQ, channel1.2.2 Response, RSP, channel1.2.3 Snoop…...
【物联网】Arduino+ESP8266物联网开发(二):控制发光二极管 按钮开关控制开关灯
【物联网】ArduinoESP8266物联网开发(一):开发环境搭建 安装Arduino和驱动 2.ESP8266基础应用 【物联网】ESP8266 开关控制 发光二极管 LED 开发软件下载地址 链接: https://pan.baidu.com/s/1BaOY7kWTvh4Obobj64OHyA?pwd3qv8 提取码: 3qv8 学习过程中会用到的基础…...
WPF向Avalonia迁移(二、一些可能使用到的库)
可能使用到的一些库 1. UI库 开源项目:https://github.com/irihitech/Semi.Avalonia 如果想引用他的DataGrid样式还需要添加Semi.Avalonia.DataGrid 2. 图表库 LiveChartsCore.SkiaSharpView.Avalonia 3.SVG库 开源项目:https://github.com/wieslaw…...
Mac navicat连接mysql出现1045 - Access denied for user ‘root‘
Mac navicat连接mysql出现1045 - Access denied for user ‘root’ 前提:如果你的mac每次开navicat都连接不上,推荐试试我这个方法 1.打开设置–>找到左下角最下面的MySQL–>点击Stop MySQL Server 2.开启一个终端,依次输入以下命令&a…...
win10电脑插入耳机,右边耳机声音比左边小很多
最近使用笔记本看视频,发现插入耳机(插入式和头戴式)后,右边耳机声音比左边耳机声音小很多很多,几乎是一边很清晰,另一边什么都听不到。 将耳机插到别人电脑上测试耳机正常,那就是电脑的问题。试…...
本文整理了Debian 11在国内的几个软件源。
1.使用说明 一般情况下,将/etc/apt/sources.list文件中Debian默认的软件仓库地址和安全更新仓库地址修改为国内的镜像地址即可,比如将deb.debian.org和security.debian.org改为mirrors.xxx.com,并使用https访问,可使用…...
2023NOIP A层联测6 数点
题目大意 给你一个排列 p p p,对于每一个 i i i,我们在平面上,放置一个点 ( i , p i ) (i,p_i) (i,pi)。对于坐标上下限都在 1 ∼ n 1\sim n 1∼n内的全体 ( n ( n 1 ) 2 ) 2 (\frac{n(n1)}{2})^2 (2n(n1))2矩形,求每个矩形…...
Jmeter 链接MySQL测试
1.环境部署 1.1官网下载MySQL Connector https://dev.mysql.com/downloads/connector/j/ 1.2 解压后,将jar放到jmeter/lib目录下 1.3 在测试计划中添加引用 2.脚本设置 2.1设置JDBC Connection Configuration 先添加一个setUp线程中,在setUp中添加“…...
jwt的了解和使用以及大致代码分析
jwt简介 以下介绍来自官网(https://jwt.io/) SON Web 令牌 (JWT) 是一种开放标准 (RFC 7519),它定义了一种紧凑且独立的方式,用于在各方之间以 JSON 对象的形式安全地传输信息。此信…...
uniapp中videojs、renderjs的使用
在uniapp中使用了某些前端库或iframe,需要操作这些库中的dom的时候, 而uni上又没有document等基础对象。也就无法操作这些dom去实现一些交互逻辑,那么,涉及到这些的前端类库就无法使用,例如html2、canvas、image、vide…...
AIGC AI绘画 Midjourney 参数大全详细列表
AIGC ChatGPT 职场案例 AI 绘画 与 短视频制作, Power BI 商业智能 68集, 数据库Mysql8.0 54集 数据库Oracle21C 142集, Office 2021实战, Python 数据分析, ETL Informatica 案例实战 Excel 2021实操,函数大全,图表大全,大屏可视化制作 加技巧500集 数据分析可视化T…...
安装hadoop,并配置hue
0、说明 对于大数据学习的初始阶段,我也曾尝试搭建相应的集群环境。通过搭建环境了解组件的一些功能、配置、原理。 在实际学习过程中,我更多的还是使用docker来快速搭建环境。 这里记录一下我搭建hadoop的过程。 1、下载hadoop 下载地址:…...
23种经典设计模式:单例模式篇(C++)
前言: 博主将从此篇单例模式开始逐一分享23种经典设计模式,并结合C为大家展示实际应用。内容将持续更新,希望大家持续关注与支持。 什么是单例模式? 单例模式是设计模式的一种(属于创建型模式 (Creational Pa…...
ros中对move_base的调用
move_base包中自带costmap2d, global planner 等功能 也可以直接调用其中make_plan进行路径规划 #include "geometry_msgs/PoseStamped.h" #includde "nav_msgs/GetPlan.h"void fillPathRequest(nav_msgs::GetPlan::Request &request, float start_x…...
Git从本地库撤销已经添加的文件或目录
场景 在提交时, 误将一个目录添加到了暂存区, 而且commit 了本地库,同批次commit 的还有其他需要提交的文件。 commit 之后发现这个目录下所有的文件都不需要提交, 现在需要撤销这个提交, 使这个目录不被push到远端库。 这里以远端服务器github 为例,在Git GUI下看到的…...
百度SEO优化的特点(方式及排名诀窍详解)
百度SEO优化的特点介绍: 百度SEO优化是指对网站进行优化,使其在百度搜索引擎中获得更好的排名,进而获取更多的流量和用户。百度SEO优化的特点是综合性强、效果持久、成本低廉、投资回报高。百度的搜索算法不断更新,所以长期稳定的…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...
让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...
使用Spring AI和MCP协议构建图片搜索服务
目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式(本地调用) SSE模式(远程调用) 4. 注册工具提…...
【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...
iview框架主题色的应用
1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题,无需引入,直接可…...
ZYNQ学习记录FPGA(一)ZYNQ简介
一、知识准备 1.一些术语,缩写和概念: 1)ZYNQ全称:ZYNQ7000 All Pgrammable SoC 2)SoC:system on chips(片上系统),对比集成电路的SoB(system on board) 3)ARM:处理器…...
土建施工员考试:建筑施工技术重点知识有哪些?
《管理实务》是土建施工员考试中侧重实操应用与管理能力的科目,核心考查施工组织、质量安全、进度成本等现场管理要点。以下是结合考试大纲与高频考点整理的重点内容,附学习方向和应试技巧: 一、施工组织与进度管理 核心目标: 规…...
前端调试HTTP状态码
1xx(信息类状态码) 这类状态码表示临时响应,需要客户端继续处理请求。 100 Continue 服务器已收到请求的初始部分,客户端应继续发送剩余部分。 2xx(成功类状态码) 表示请求已成功被服务器接收、理解并处…...
