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

归并排序 nO(lgn)

大家好,我是蓝胖子,我一直相信编程是一门实践性的技术,其中算法也不例外,初学者可能往往对它可望而不可及,觉得很难,学了又忘,忘其实是由于没有真正搞懂算法的应用场景,所以我准备出一个系列,囊括我们在日常开发中常用的算法,并结合实际的应用场景,真正的感受算法的魅力。

代码已经上传github

https://github.com/HobbyBear/codelearning/tree/master/mergesort

算法原理

每每实现算法的时候,我总是倾向于用文字将算法的逻辑描述出来,当你能清晰的描述算法逻辑的时候,实现起来就是水到渠成的事情。

所以,我们接下来首先看下归并排序的算法逻辑。归并排序的时间复杂度是nO(lg n),它要求每次 将数组一分为二,被分割的数组又一分为二直至不能被分割,最后由底向上进行两两合并。你可以看到,假设数组长度是n,整个过程一共有lg n层,每一层需要对n个元素进行合并,所以时间复杂度是nO(lg n)。如下图所示:

Pasted image 20230905144638.png

合并的过程是将合并的两个有序数组的元素变成一个有序数组的过程,我们把这个过程称为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时,得到逆序对的数量,如下,

Pasted image 20230905150954.png

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)

大家好&#xff0c;我是蓝胖子&#xff0c;我一直相信编程是一门实践性的技术&#xff0c;其中算法也不例外&#xff0c;初学者可能往往对它可望而不可及&#xff0c;觉得很难&#xff0c;学了又忘&#xff0c;忘其实是由于没有真正搞懂算法的应用场景&#xff0c;所以我准备出…...

数据库Mysql三大引擎(InnoDB、MyISAM、 Memory)与逻辑架构

MySQL数据库及其分支版本主要的存储引擎有InnoDB、MyISAM、 Memory等。简单地理解&#xff0c;存储引擎就是指表的类型以及表在计算机上的存储方式。存储引擎的概念是MySQL的特色&#xff0c;使用的是一个可插拔存储引擎架构&#xff0c;能够在运行的时候动态加载或者卸载这些存…...

Python数据分析实战-实现Mann-Whitney U检验(附源码和实现效果)

实现功能 使用scipy.stats模块中的mannwhitneyu函数来实现Mann-Whitney U检验&#xff0c;该检验用于比较两个独立样本的分布是否有显著差异。 实现代码 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物联网开发(一)&#xff1a;开发环境搭建 安装Arduino和驱动 2.ESP8266基础应用 【物联网】ESP8266 开关控制 发光二极管 LED 开发软件下载地址 链接: https://pan.baidu.com/s/1BaOY7kWTvh4Obobj64OHyA?pwd3qv8 提取码: 3qv8 学习过程中会用到的基础…...

WPF向Avalonia迁移(二、一些可能使用到的库)

可能使用到的一些库 1. UI库 开源项目&#xff1a;https://github.com/irihitech/Semi.Avalonia 如果想引用他的DataGrid样式还需要添加Semi.Avalonia.DataGrid 2. 图表库 LiveChartsCore.SkiaSharpView.Avalonia 3.SVG库 开源项目&#xff1a;https://github.com/wieslaw…...

Mac navicat连接mysql出现1045 - Access denied for user ‘root‘

Mac navicat连接mysql出现1045 - Access denied for user ‘root’ 前提&#xff1a;如果你的mac每次开navicat都连接不上&#xff0c;推荐试试我这个方法 1.打开设置–>找到左下角最下面的MySQL–>点击Stop MySQL Server 2.开启一个终端&#xff0c;依次输入以下命令&a…...

win10电脑插入耳机,右边耳机声音比左边小很多

最近使用笔记本看视频&#xff0c;发现插入耳机&#xff08;插入式和头戴式&#xff09;后&#xff0c;右边耳机声音比左边耳机声音小很多很多&#xff0c;几乎是一边很清晰&#xff0c;另一边什么都听不到。 将耳机插到别人电脑上测试耳机正常&#xff0c;那就是电脑的问题。试…...

本文整理了Debian 11在国内的几个软件源。

1&#xff0e;使用说明 一般情况下&#xff0c;将/etc/apt/sources.list文件中Debian默认的软件仓库地址和安全更新仓库地址修改为国内的镜像地址即可&#xff0c;比如将deb.debian.org和security.debian.org改为mirrors.xxx.com&#xff0c;并使用https访问&#xff0c;可使用…...

2023NOIP A层联测6 数点

题目大意 给你一个排列 p p p&#xff0c;对于每一个 i i i&#xff0c;我们在平面上&#xff0c;放置一个点 ( 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矩形&#xff0c;求每个矩形…...

Jmeter 链接MySQL测试

1.环境部署 1.1官网下载MySQL Connector https://dev.mysql.com/downloads/connector/j/ 1.2 解压后&#xff0c;将jar放到jmeter/lib目录下 1.3 在测试计划中添加引用 2.脚本设置 2.1设置JDBC Connection Configuration 先添加一个setUp线程中&#xff0c;在setUp中添加“…...

jwt的了解和使用以及大致代码分析

jwt简介 以下介绍来自官网&#xff08;https://jwt.io/&#xff09; SON Web 令牌 &#xff08;JWT&#xff09; 是一种开放标准 &#xff08;RFC 7519&#xff09;&#xff0c;它定义了一种紧凑且独立的方式&#xff0c;用于在各方之间以 JSON 对象的形式安全地传输信息。此信…...

uniapp中videojs、renderjs的使用

在uniapp中使用了某些前端库或iframe&#xff0c;需要操作这些库中的dom的时候&#xff0c; 而uni上又没有document等基础对象。也就无法操作这些dom去实现一些交互逻辑&#xff0c;那么&#xff0c;涉及到这些的前端类库就无法使用&#xff0c;例如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、说明 对于大数据学习的初始阶段&#xff0c;我也曾尝试搭建相应的集群环境。通过搭建环境了解组件的一些功能、配置、原理。 在实际学习过程中&#xff0c;我更多的还是使用docker来快速搭建环境。 这里记录一下我搭建hadoop的过程。 1、下载hadoop 下载地址&#xff1a;…...

23种经典设计模式:单例模式篇(C++)

前言&#xff1a; 博主将从此篇单例模式开始逐一分享23种经典设计模式&#xff0c;并结合C为大家展示实际应用。内容将持续更新&#xff0c;希望大家持续关注与支持。 什么是单例模式&#xff1f; 单例模式是设计模式的一种&#xff08;属于创建型模式 (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优化的特点介绍&#xff1a; 百度SEO优化是指对网站进行优化&#xff0c;使其在百度搜索引擎中获得更好的排名&#xff0c;进而获取更多的流量和用户。百度SEO优化的特点是综合性强、效果持久、成本低廉、投资回报高。百度的搜索算法不断更新&#xff0c;所以长期稳定的…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...

uniapp 小程序 学习(一)

利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 &#xff1a;开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置&#xff0c;将微信开发者工具放入到Hbuilder中&#xff0c; 打开后出现 如下 bug 解…...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...

python打卡day49@浙大疏锦行

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 一、通道注意力模块复习 & CBAM实现 import torch import torch.nn as nnclass CBAM(nn.Module):def __init__…...