欢迎阅读愿旖旎· 个人主页学习专栏《算法专栏》《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剩余元素没写回填时只覆盖了部分位置后半段仍是旧数据——错误表现为部分有序而非全乱。在相等时先取左段保持相等元素的相对顺序稳定会先取右段稳定性被破坏。本题只要求升序不需要稳定但写是归并排序的标准做法为多关键字排序等扩展留余地。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨