7.4 分治-归并：LeetCode 912.排序数组

---

1. 标题链接

LeetCode 912. 排序数组
标题要求：给定一个整数数组 nums，返回该数组按升序排列后的结果。要求时间复杂度为 O(n log n)，空间复杂度只管低。

---

2. 标题描述

• 输入：一个整数数组 nums，例如 [5,2,3,1]。
  
• 输出：升序排列后的数组，例如 [1,2,3,5]。
  
• 束缚条件：
  
  
  
  • 1 <= nums.length <= 5e4
    
  • -1e5 <= nums <= 1e5
    
  
  

---

3. 示例分析

示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
分治过程分解：

• 分解：将数组分为 [5,2] 和 [3,1]。
  
• 递归排序：左数组排序为 [2,5]，右数组排序为 [1,3]。
  
• 合并：合并两个有序数组 [2,5] 和 [1,3]，得到终极结果 [1,2,3,5]。
  

示例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
关键点：归并排序是稳固的，相等的元素在合并时保持原有次序。

---

4. 算法思路

分治思想：分解 → 排序 → 合并

• 分解：将数组递归地二分，直到子数组长度为1（天然有序）。
  
• 排序子数组：对左右子数组分别递归排序。
  
• 合并：将两个有序子数组合并为一个有序数组。
  

合并操作的关键步调

• 双指针遍历：用指针 cur1 和 cur2 分别遍历左、右子数组。
  
• 临时数组存储：将较小元素按序存入临时数组 tmp。
  
• 处理剩余元素：若某一子数组遍历未完成，直接追加剩余元素。
  
• 数据回写：将临时数组中的数据复制回原数组对应的区间。
  

---

5. 边界条件与留意事项

• 递归停止条件：
  
  
  
  • 当 left >= right 时停止递归（子数组长度为1或0）。
    
  
  
• 索引计算：
  
  
  
  • 中间点计算：mid = (left + right) / 2 可能溢出，建议改为 left + (right - left) / 2。
    
  • 临时数组偏移：合并后数据回写时，通过 j - left 计算原数组的偏移量。
    
  
  
• 稳固性保证：
  
  
  
  • 合并时使用 nums[cur1] <= nums[cur2]，保留相等元素的原始次序。
    
  
  
• 复杂度分析：
  
  
  
  • 时间复杂度：O(n log n)（递归深度为 log n，每层合并操作 O(n)）。
    
  • 空间复杂度：O(n)（临时数组 tmp 占用额外空间）。
    
  
  

---

6. 代码实现与逐行剖析

1. class Solution {
2. public:
3.     vector<int> tmp; // 全局临时数组，避免递归中反复开辟内存
4.     vector<int> sortArray(vector<int>& nums) {
5.         tmp.resize(nums.size());      // 预分配临时数组空间
6.         mergeSort(nums, 0, nums.size() - 1);
7.         return nums;
8.     }
10.     void mergeSort(vector<int>& nums, int left, int right) {
11.         if (left >= right) return;    // 终止条件：子数组长度为0或1
13.         int mid = (left + right) / 2; // 计算中间点（建议改为防溢出写法）
14.         mergeSort(nums, left, mid);   // 递归排序左半部分
15.         mergeSort(nums, mid + 1, right); // 递归排序右半部分
17.         // 合并两个有序子数组
18.         int cur1 = left, cur2 = mid + 1, i = 0;
19.         while (cur1 <= mid && cur2 <= right) {
20.             // 稳定排序：保留相等元素的原始顺序
21.             tmp[i++] = (nums[cur1] <= nums[cur2]) ? nums[cur1++] : nums[cur2++];
22.         }
23.         // 处理左子数组剩余元素
24.         while (cur1 <= mid) tmp[i++] = nums[cur1++];
25.         // 处理右子数组剩余元素
26.         while (cur2 <= right) tmp[i++] = nums[cur2++];
27.         
28.         // 将临时数组复制回原数组
29.         for (int j = left; j <= right; j++) {
30.             nums[j] = tmp[j - left]; // 计算偏移量
31.         }
32.     }
33. };

复制代码

代码剖析

• 全局临时数组 tmp：
  
  
  
  • 预分配空间制止递归中频繁申请内存，提升性能。
    
  
  
• 递归分解与排序：
  
  
  
  • mergeSort 递归分割数组，直到子数组长度为1。
    
  
  
• 合并逻辑：
  
  
  
  • 双指针遍历：cur1 和 cur2 分别指向左、右子数组的起始位置，比较后插入 tmp。
    
  • 剩余元素处理：直接追加未遍历完的子数组元素。
    
  • 数据回写：通过 j - left 将 tmp[0..i-1] 对应到原数组的 [left, right] 区间。
    
  
  
• 潜伏优化点：
  
  
  
  • 中间点防溢出：将 mid 计算改为 left + (right - left) / 2。
    
  • 小数组优化：当子数组长度较小时（如 <= 64），可改用插入排序减少递归开销。
    
  
  

---

总结

归并排序通过分治策略实现了稳固的 O(n log n) 排序，尤其适合处理大规模数据。其焦点在于递归分解与合并操作，合并时需留意稳固性和临时数组的空间管理。本文代码通过预分配全局临时数组优化了空间效率，但在极端情况下需考虑中间点计算的溢出题目。理解归并排序的实现细节，有助于把握分治思想在其他算法中的应用（如逆序对统计、外部排序等）。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。