👋 欢迎阅读
🔥 愿旖旎 · 个人主页
📘 学习专栏： 《算法专栏》《LangChain学习》《贪心算法》
🌄 钱塘江上潮信来，今日方知我是我
✨当前学习内容：《快速排序》
一.题目
🎯 欢迎来到「排序数组」题解之旅！ 本文将带你从"把两摞已排好的牌合并成一摞"这一直观场景出发，深入理解归并排序（分治）的巧妙运用，并掌握如何递归二分 + 双指针合并来在 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]与[mid+1, 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] ✅ |
3、正确性说明（简单版本）
- 拆分正确：每次取中点把区间一分为二（
[left, mid]与[mid+1, 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)（辅助数组
tmp）+ O(log n)（递归栈）。 - 关键操作：
mid = left + (right - left) / 2;（安全取中点）、if (nums[cur1] <= nums[cur2]) tmp[i++] = nums[cur1++];（双指针取小）、nums[i] = tmp[i - left];（偏移回填）。
📌 例子：tmp 为什么要"一次分配、反复复用"
若把
tmp声明成局部数组、每次合并都新建vector<int>(len)：n = 5×10⁴时递归会产生约 n-1 次合并，即 5 万次堆分配，累计分配/释放的数据量约 O(n log n)，且频繁申请释放会拖慢程序、加剧内存碎片。作为成员变量只resize一次，所有轮次复用同一块空间，分配次数从 O(n) 降到 1，是归并排序的常见优化。
5、返回值（目标映射）
- 返回
nums：原地排序完成后的原数组（mergeSort已把结果回填进去），对应题目"返回排序后的数组"。
三.代码
class Solution
{
vector<int> tmp; // 辅助数组：所有合并轮次复用（只分配一次）
public:
vector<int> sortArray(vector<int>& nums)
{
int n = nums.size();
tmp.resize(n); // 一次性开好，避免每次递归都分配
mergeSort(nums, 0, n - 1); // 对闭区间 [0, n-1] 归并排序
return nums; // 结果已回填到 nums 中
}
void mergeSort(vector<int>& nums, int left, int right)
{
// 1. 递归终止：区间只剩 0 或 1 个元素，天然有序
if (left >= right)
{
return;
}
// 2. 取中点（防溢出写法），对半拆分
int mid = left + (right - left) / 2;
// 3. 分别排序左右两段：[left, mid] 与 [mid+1, 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 分别对应"左段剩余"与"右段剩余"，一个都不能少。
难点3：mid 取整与区间划分必须配套
int mid = left + (right - left) / 2;
mergeSort(nums, left, mid); // 左段 [left, mid]
mergeSort(nums, mid + 1, right); // 右段 [mid+1, right]mid 下取整，故左段是 [left, mid]、右段是 [mid+1, 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]。请问**<=与<对排序结果有何影响**？本题需要稳定吗？ mid是下取整，区间划分为[left, mid]与[mid+1, right]。请问若把划分写成[left, mid-1]与[mid, right]会发生什么？
如果你觉得本文对你有所帮助，欢迎：
👍 点赞 / 收藏 👤 关注作者，获取更多题解 💬 留言交流你的疑问或优化思路
📌 深入思考答案
- "单元素天然有序"是递归的终止条件——它把"排序整个数组"分解为"排序单元素"这一不需要任何操作的最小单位，再靠合并逐层回溯，这是分治能够收敛的根本。
tmp本轮从下标 0 写起，而nums的目标区间起点是left，两者起点错开left个位置；不减left会读到tmp中不属于本轮的数据（或上一轮旧值），回填错乱。- 当某一子段先耗尽时触发收尾（另一段还有剩余）。省略后，主循环只把"能比较的部分"写入
tmp，剩余元素没写，回填时只覆盖了部分位置，后半段仍是旧数据——错误表现为部分有序而非全乱。 <=在相等时先取左段，保持相等元素的相对顺序（稳定）；<会先取右段，稳定性被破坏。本题只要求升序，不需要稳定，但写<=是归并排序的标准做法，为多关键字排序等扩展留余地。mid下取整时，[left, mid-1]在left == mid时为空、[mid, right]仍是原区间，递归区间不缩小，导致无限递归直至栈溢出；必须配套[left, mid]与[mid+1, right]。
祝你在 算法之路 上越走越稳，早日攻克每一道难题！下次见 🚀✨
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/2601_96587588/article/details/168236015
