归并排序 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优化的特点是综合性强、效果持久、成本低廉、投资回报高。百度的搜索算法不断更新,所以长期稳定的…...
CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...
【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习
禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...
安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...
push [特殊字符] present
push 🆚 present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中,push 和 present 是两种不同的视图控制器切换方式,它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...
【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看
文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...
【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)
前言: 双亲委派机制对于面试这块来说非常重要,在实际开发中也是经常遇见需要打破双亲委派的需求,今天我们一起来探索一下什么是双亲委派机制,在此之前我们先介绍一下类的加载器。 目录 编辑 前言: 类加载器 1. …...
华为OD机试-最短木板长度-二分法(A卷,100分)
此题是一个最大化最小值的典型例题, 因为搜索范围是有界的,上界最大木板长度补充的全部木料长度,下界最小木板长度; 即left0,right10^6; 我们可以设置一个候选值x(mid),将木板的长度全部都补充到x,如果成功…...
