归并排序 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优化的特点是综合性强、效果持久、成本低廉、投资回报高。百度的搜索算法不断更新,所以长期稳定的…...

376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...
基于数字孪生的水厂可视化平台建设:架构与实践
分享大纲: 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年,数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段,基于数字孪生的水厂可视化平台的…...

Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
【生成模型】视频生成论文调研
工作清单 上游应用方向:控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...