欢迎阅读愿旖旎· 个人主页学习专栏《算法专栏》《LangChain学习》《贪心算法》 钱塘江上潮信来今日方知我是我✨当前学习内容《归并排序》一.题目912. 排序数组 - 力扣LeetCode 欢迎来到「排序数组」题解之旅本文将带你从把两摞已排好的牌合并成一摞这一直观场景出发深入理解归并排序分治的巧妙运用并掌握如何递归二分 双指针合并来在 O(n log n) 内完成排序。在开始之前建议你先了解题目背景这是 LeetCode 912 题给定整数数组nums要求按升序排序并返回不能使用内置排序函数数组长度可达5×10⁴。本质上排序可以分而治之——把数组拆到只剩单个元素天然有序再两两合并成有序序列。明确学习目标掌握归并排序的递归划分与合并技术理解辅助数组tmp的偏移回填与收尾 while的作用并熟练处理递归终止与稳定性等边界情况。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如nums [5,2,3,1]输出[1,2,3,5]。本文将从问题转化、递归分治、双指针合并、边界防护到代码实现层层递进。即使你对归并排序还不熟悉我们也会从先拆成一个个再两两拼回有序这一直觉出发让你轻松抓住核心思想——分到最细合而有序。现在让我们一起递归拆分、双指针合并把数组排好序吧 二、算法分析1. 问题分析前置分析题目要求对nums升序排序并返回禁止调用内置排序长度可达5×10⁴。关键约束不能直接用sort数据量大O(n²) 算法会超时要求最坏情况也稳定在 O(n log n)。核心思路归并排序——递归把数组对半拆分到单元素天然有序再在回溯时把相邻两段双指针合并最坏、平均都是 O(n log n)且天然稳定。 例子为什么是归并而不是快排/冒泡nums [5,2,4,1]冒泡需约n²/2次比较n 5×10⁴时约1.25×10⁹次必超时快速排序平均 O(n log n)但最坏 O(n²)如已排序数组取末端为基准。归并排序无论输入如何都是 O(n log n)且用还能保持稳定——在禁用内置排序 大数据量的约束下最稳妥。2. 算法策略归并排序 · 递归分治 双指针合并核心步骤开辅助数组成员tmp一次性resize(n)供所有合并轮次复用。递归终止if (left right) return;区间只剩 0/1 个元素天然有序。递归拆分取中点mid left (right - left) / 2分别排序[left, mid]与[mid1, right]。双指针合并cur1从左段起点、cur2从右段起点每次取较小者写入tmp保证稳定。收尾搬运某一段先耗尽后把另一段剩余元素依次搬入tmp。回填原数组nums[i] tmp[i - left]把本轮合并结果写回。 示例nums [5,2,4,1]阶段区间操作结果拆分[0,3]中点 1拆成 [0,1] 与 [2,3]—拆分[0,1]中点 0拆成 [0,0] 与 [1,1]单元素天然有序合并[0,1]合并5与2取 2再取 5[2,5]拆分[2,3]中点 2拆成 [2,2] 与 [3,3]单元素天然有序合并[2,3]合并4与1取 1再取 4[1,4]合并[0,3]双指针合并[2,5]与[1,4]1、2、4、5[1,2,4,5]✅两次小合并产出[2,5]与[1,4]最后一次大合并把两段按序交错取出得到[1,2,4,5]✅。3. 正确性说明拆分正确每次取中点把区间一分为二[left, mid]与[mid1, right]两段不重不漏递归直到单元素终止。合并正确双指针从两段起点推进每次取较小者写入tmp保证合并结果的单调性保证相等时先取左段维持稳定性。收尾完备某个指针先越界后另一段的剩余元素必然都更大或相等直接依次搬运即可不会遗漏。回填正确tmp本轮从下标 0 写起回填时用tmp[i - left]精确偏移nums的[left, right]段被完整覆盖为本轮合并结果。 例子为什么收尾 while不能省略合并[1,2]与[3,4]主循环依次取1、2后左段立即耗尽cur1 mid此时右段的3、4还没写入——若只有主循环tmp只写入了[1,2]回填后nums的后两位就是旧数据排序错误。两个收尾 while 专门搬运另一段的剩余元素缺一不可。4. 实现细节初始化tmp作为成员变量在sortArray中resize(n)一次分配mergeSort(nums, 0, n-1)区间为闭区间[left, right]。边界防护if (left right) return;用比更防御mid left (right - left) / 2防溢出的写法tmp[i - left]回填时偏移必须减 left。复杂度时间 O(n log n)共 log n 层每层合并总代价 O(n)空间 O(n)辅助数组tmpO(log n)递归栈。关键操作mid left (right - left) / 2;安全取中点、if (nums[cur1] nums[cur2]) tmp[i] nums[cur1];双指针取小、nums[i] tmp[i - left];偏移回填。 例子tmp 为什么要一次分配、反复复用若把tmp声明成局部数组、每次合并都新建vectorint(len)n 5×10⁴时递归会产生约n-1 次合并即5 万次堆分配累计分配/释放的数据量约 O(n log n)且频繁申请释放会拖慢程序、加剧内存碎片。作为成员变量只resize一次所有轮次复用同一块空间分配次数从 O(n) 降到1。5. 返回值返回nums原地排序完成后的原数组mergeSort已把结果回填进去对应题目返回排序后的数组。三.代码class Solution { vectorint tmp; // 辅助数组所有合并轮次复用只分配一次 public: vectorint sortArray(vectorint nums) { int n nums.size(); tmp.resize(n); // 一次性开好避免每次递归都分配 mergeSort(nums, 0, n - 1); // 对闭区间 [0, n-1] 归并排序 return nums; // 结果已回填到 nums 中 } void mergeSort(vectorint nums, int left, int right) { // 1. 递归终止区间只剩 0 或 1 个元素天然有序 if (left right) { return; } // 2. 取中点防溢出写法对半拆分 int mid left (right - left) / 2; // 3. 分别排序左右两段[left, mid] 与 [mid1, right] mergeSort(nums, left, mid); mergeSort(nums, mid 1, right); // 4. 双指针合并从两段起点出发每次取较小者写入 tmp int cur1 left; // 左段指针 int cur2 mid 1; // 右段指针 int i 0; // tmp 的写入位置从 0 开始 while (cur1 mid cur2 right) { if (nums[cur1] nums[cur2]) // 用 保证稳定性 { tmp[i] nums[cur1]; } else { tmp[i] nums[cur2]; } } // 5. 收尾把尚未耗尽的另一段剩余元素直接搬入 tmp while (cur1 mid) { tmp[i] nums[cur1]; } while (cur2 right) { tmp[i] nums[cur2]; } // 6. 回填tmp 从 0 写起故 nums[i] 对应 tmp[i - left] for (int k left; k right; k) { nums[k] tmp[k - left]; } } };四、易错点分析难点1回填时的偏移tmp[i - left]for (int i left; i right; i) { nums[i] tmp[i - left]; }tmp每轮合并都从下标 0 开始写i初始为 0而nums的目标区间是[left, right]两者起点不同因此回填必须减去left偏移。若写成nums[i] tmp[i]当left 0时会读到tmp中不属于本段的数据本轮只写了tmp[0 .. right-left]导致元素错乱同时i可能超出本轮写入范围读到上一轮的旧值。tmp 从 0 写、回填减 left是一套配套约定也可改成从 left 写、回填直接对应但两者不能混用。难点2两个收尾while缺一不可while (cur1 mid) tmp[i] nums[cur1]; while (cur2 right) tmp[i] nums[cur2];主循环在任一段耗尽时停止此时另一段可能还有剩余元素未被写入tmp。合并[1,2]与[3,4]时主循环取完1、2就退出3、4必须靠第二个收尾while搬入省略后tmp后半段是旧数据回填即出错。两个while分别对应左段剩余与右段剩余一个都不能少。难点3mid取整与区间划分必须配套int mid left (right - left) / 2; mergeSort(nums, left, mid); // 左段 [left, mid] mergeSort(nums, mid 1, right); // 右段 [mid1, right]mid下取整故左段是[left, mid]、右段是[mid1, right]两段不重不漏。若划分写成[left, mid-1]与[mid, right]当left mid区间长 2时左段为空、右段仍是原区间递归永远不缩小 → 无限递归栈溢出。另外left (right - left) / 2避免left right溢出是安全取中点的标准写法。难点4与决定排序是否稳定if (nums[cur1] nums[cur2]) tmp[i] nums[cur1];相等时用会优先取左段元素而左段元素在原数组中本就位于右段之前因此相等元素的相对顺序得以保持——这就是稳定性。若写成相等时会先取右段相对顺序被颠倒变为不稳定排序。本题只要求升序稳定性不影响正确性但归并排序的稳定性是它的重要优势多关键字排序时必需写是良好习惯。难点5递归终止条件left right不能漏if (left right) { return; }递归的分到最细终点是区间只剩 1 个元素此时天然有序无需合并。若漏掉这个终止条件mergeSort会无限自我调用空区间不收敛直接栈溢出崩溃。用而非是防御性写法即使区间意外变空如错误划分也能正确返回而不越界。五、流程图 闭幕 恭喜你完成了「排序数组」问题的学习为了巩固知识并进一步拓展建议你 动手实践在 LeetCode 上提交代码尝试不同的测试用例。 深入思考本题采用归并排序把数组拆到单元素再合并。请问**单元素天然有序这一性质在算法中扮演什么角色它是递归的什么tmp每轮合并从下标 0 开始写回填用tmp[i - left]。请问为什么要减left不减会发生什么两个收尾while缺一不可。请问在什么情况下会触发收尾省略后为什么只丢后半段而不是全部代码用nums[cur1] nums[cur2]。请问**与对排序结果有何影响**本题需要稳定吗如果你觉得本文对你有所帮助欢迎 点赞 / 收藏 关注作者获取更多题解 留言交流你的疑问或优化思路 深入思考答案单元素天然有序是递归的终止条件——它把排序整个数组分解为排序单元素这一不需要任何操作的最小单位再靠合并逐层回溯这是分治能够收敛的根本。tmp本轮从下标 0 写起而nums的目标区间起点是left两者起点错开left个位置不减left会读到tmp中不属于本轮的数据或上一轮旧值回填错乱。当某一子段先耗尽时触发收尾另一段还有剩余。省略后主循环只把能比较的部分写入tmp剩余元素没写回填时只覆盖了部分位置后半段仍是旧数据——错误表现为部分有序而非全乱。在相等时先取左段保持相等元素的相对顺序稳定会先取右段稳定性被破坏。本题只要求升序不需要稳定但写是归并排序的标准做法为多关键字排序等扩展留余地。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨
企业数字化 ERP 产品动态
相关推荐
AI帮我WORD改全框表开放表是一种什么体验 接上一篇。
三线表改对了,我更自信了。
我跟AI说,再给我改成全框表。
话说回来,也就人能对AI这样了,如果换成是人,这要求真是冒犯了。
丝滑的全框表
结果,AI很丝滑,一遍就出了。
想想也知道&… · 2026/11/21 3:38:56
八、搞懂安全攸关软件设计:DO-178B三大支柱、A~E五级目标数与容错架构全景 搞懂安全攸关软件设计:DO-178B三大支柱、A~E五级目标数与容错架构全景
我们在互联网或商用系统的日常开发中,即使代码偶发空指针或者死锁,通常也不过是弹个报错页面、提示用户“系统繁忙稍后重试”,晚上热修复发个补丁即可。
但当… · 2026/11/21 3:38:57
spirngSecurity 鉴权教程02 文章目录spirngSecurity 鉴权教程02使用 MyBatis-Plus1. 引入依赖2. 安装 IDEA 插件3. 配置数据源4. 准备数据表利用 MyBatisX 生成 Mapper、Service、Controller、POJO重写userDetailsService1. 为什么需要重写 UserDetailsService2. 编写实现类3. 配置 PasswordEncoder4. 生成… · 2026/11/8 7:51:08
北京电工证难考不?千万别踩坑,实操考试全攻略来了 北京电工证难考不?千万别踩坑,实操考试全攻略来了 实操考试心里没底怕挂科,这几乎是每个想考北京电工证的人的真实写照。特别是对于南阳劳务班组的负责人来说,电工证不仅关乎个人职业发展,更关系到班组的施工资质和项目承接能力。如果因为一次实操考试没… · 2026/11/21 3:38:23
海安电工证考试报名多久拿证?外省证能转过来吗? 海安电工证考试报名多久拿证?外省证能转过来吗? 之前考的证在外省能不能转过来?这几乎是每个准备报考或者已经报考海安电工证考试报名的人最关心的问题。其实,外省考的电工证是可以转过来的,但前提是你的证是在国家安全生产考试网备案并可查询的。而且,… · 2026/11/21 3:38:23
海安电工证考试报名合格标准与通过率,全国通用怎么考更稳妥 海安电工证考试报名合格标准与通过率,全国通用怎么考更稳妥 怕考不过白交培训费?海安电工证考试报名前必须知道的真相来了。很多学员一上来就报名,结果考试没过,培训费打了水漂,甚至耽误了工作机会。别急,这篇文章讲透合格标准、通过率和备考策略,助你… · 2026/11/21 3:38:23
江都考电工证难吗怎么报名全攻略 江都考电工证难吗怎么报名全攻略 之前考的证在外省能不能转过来,这是很多人在考虑考电工证时的第一反应。尤其是那些已经在外地工作、但打算回江都发展的人,最担心的就是证书的 有效性与可转移性… · 2026/11/21 3:38:23
特种作业电工证考接线证怎么转异地,值不值得考 特种作业电工证考接线证怎么转异地,值不值得考 学历不高怕报不上名?特种作业电工证考接线证怎么转异地?值不值得考?这些问题困扰着很多人,尤其是像洛阳涧西区应届工程类毕业生这样的初入职场人群。特种作业电工证在实际工作中是必须的,但报名条件、流程… · 2026/11/21 3:37:23
长春初级电工证怎么考?通过率揭秘全在这里 长春初级电工证怎么考?通过率揭秘全在这里 之前考的证在外省能不能转过来?这几乎是每个想从事电工工作的人都会问的问题。特别是那些在外地打拼多年、手里握着一张“外地电工证”的人,到了长春想继续干这一行,第一反应就是“我的证能用吗?”。今天我们就… · 2026/11/20 16:18:19
国内电工证报考条件与考试时间 低压电工证怎么考?学历不高也能报名,官方报名入口全在这 你是不是经常听说“电工证是入行门槛”,但又担心自己学历不够、经验不足,根本报不了名?别急,今天就带你从零了解【国内电工证】的报考流程、考试内容,还有怎么在 官方报名入口… · 2026/11/20 18:25:07
电工作业时如何断电?电子证书到底能不能全国通用? 电工作业时如何断电?电子证书到底能不能全国通用? 实操考试心里没底怕挂科,特别是电工作业时如何断电这一操作,不仅关系到你能不能拿到证书,更关系到以后能不能顺利上岗。很多人觉得这不过就是“断个电”,但其实这里面的门道可不少,稍有不慎就可能出错… · 2026/11/20 17:56:32
电工证征求意见2026河南最新政策怎么应对?学历不高也能考! 电工证征求意见2026河南最新政策怎么应对?学历不高也能考! 你是不是也担心自己学历不高, 怕报不上名 ?尤其是像焦作水利工程这样的从业者,常年在一线作业,但证书却成了晋升、转岗、接项目的关键门槛。 2026河南最新政策… · 2026/11/21 0:00:17
电工证征求意见怎么填?含金量高不高?济源电工朋友看过来 电工证征求意见怎么填?含金量高不高?济源电工朋友看过来 不知道去哪报名怕被中介坑,电工证征求意见填错了不仅白费钱,还可能影响后续考试和工作。最近很多济源的电工朋友都在问: 电工证征求意见怎么填… · 2026/11/21 0:00:17
房建企业特种工考前押题怎么找?别让培训费打了水漂 房建企业特种工考前押题怎么找?别让培训费打了水漂 怕考不过白交培训费?房建企业特种工考试难度高、题型多,很多人报名后才发现没有合适的复习资料,最终考试落榜,白白浪费了时间和金钱。别担心,掌握【考前押题】的技巧,能让你事半功倍,顺利通过考试。… · 2026/11/21 0:00:17
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试 /* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/20 10:25:45
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析 /* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/20 10:25:54
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案 /* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/20 10:26:03