本文讲解归并排序的分治思想及其进阶应用。内容包括归并排序基础实现、数组逆序对统计、计算右侧小于当前元素的个数以及翻转对问题。通过分析归并排序合并过程中的特性，将时间复杂度从 O(n^2) 优化至 O(n log n)。文中提供了详细的 C++ 代码实现、易错点提示及复杂度分析，帮助读者深入理解分治策略在算法题中的应用。
归并排序是经典的分治法应用，其核心在于'分而治之'的思想。通过不断划分，将一个复杂问题逐步拆解成若干规模更小的子问题，以递归方式求解，再将解合并，从而解决初始问题。本文将围绕归并排序的基本原理，结合排序数组的题目，深入剖析归并排序在分治中的实际应用。
题目链接：912. 排序数组
题目描述：
给定一个整数数组 nums，请将该数组按升序排列。
示例 1：
nums = [5,2,3,1][1,2,3,5]示例 2：
nums = [5,1,1,2,0,0][0,0,1,1,2,5]算法思路：
归并排序的过程充分体现了'分而治之'的思想，基本步骤分为以下两部分：
具体步骤：
[left, mid] 和 [mid + 1, right] 两部分。tmp 中。tmp 数组的内容拷贝回原数组。class Solution {
vector<int> tmp; // 临时数组用于存储合并结果
public:
vector<int> sortArray(vector<int>& nums) {
tmp.resize(nums.size());
mergeSort(nums, 0, nums.size() - 1);
return nums;
}
// 归并排序
void mergeSort(vector<int>& nums, int left, int right) {
if (left >= right) return; // 递归终止条件
// 1. 分区
int mid = (left + right) / 2;
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
// 2. 合并两个已排序数组
int cur1 = left, cur2 = mid + 1, i = 0;
while (cur1 <= mid && cur2 <= right) {
tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
}
while (cur1 <= mid) tmp[i++] = nums[cur1++]; // 左边剩余部分
while (cur2 <= right) tmp[i++] = nums[cur2++]; // 右边剩余部分
// 3. 拷贝回原数组
for (int j = 0; j < i; ++j) {
nums[left + j] = tmp[j];
}
}
};
mergeSort 函数中，left >= right 时停止递归，以防止无穷递归导致的栈溢出。cur1 和 cur2 分别指向左、右子数组的起始位置，使用 tmp 存储合并结果。确保在所有元素都合并后，将 tmp 拷贝回 nums 中。tmp 存储每一轮合并结果，以确保排序结果被完整保留到下一轮递归。O(n log n)。每轮合并的时间复杂度为 O(n)，分区深度为 log n。O(n)，临时数组 tmp 占用额外空间。题目链接：剑指 Offer 51. 数组中的逆序对
题目描述：
在一个数组中的两个数字，如果前面的一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1：
[7,5,6,4]5算法思路：
归并排序求逆序数是经典的方法。在归并排序的合并过程中，我们可以顺便统计出逆序对的数量，这样可以避免暴力统计的 O(n^2) 时间复杂度。
逆序对的产生方式可分为三种情况：
归并排序过程可以分为两个步骤：
left = [5, 7, 9] 和 right = [4, 5, 8]。
目标是计算在合并的过程中 left 中的元素大于 right 中的元素的情况数量。cur1 遍历 left 数组，cur2 遍历 right 数组。
定义 ret 记录逆序对的数量，help 数组临时存储排序的结果。
left[cur1] 和 right[cur2]，如果 left[cur1] > right[cur2]，则意味着从 cur1 到末尾的元素都大于 right[cur2]（因为 left 是有序的）。我们可以确定逆序对数量并将结果累加到 ret。left[cur1] <= right[cur2]，则将 left[cur1] 添加到 help 数组中。help 数组即可，不会再产生新的逆序对。class Solution {
int tmp[50010]; // 临时数组
public:
int reversePairs(vector<int>& nums) {
return mergeSort(nums, 0, nums.size() - 1);
}
int mergeSort(vector<int>& nums, int left, int right) {
if (left >= right) return 0; // 递归终止条件
int ret = 0;
// 1. 找中间点，将数组分成两部分
int mid = (left + right) >> 1;
// 2. 左、右部分的逆序对数量
ret += mergeSort(nums, left, mid);
ret += mergeSort(nums, mid + 1, right);
// 3. 合并并统计逆序对数量
int cur1 = left, cur2 = mid + 1, i = 0;
while (cur1 <= mid && cur2 <= right) {
if (nums[cur1] <= nums[cur2]) {
tmp[i++] = nums[cur1++]; // 左侧元素较小，无逆序对
} else {
ret += mid - cur1 + 1; // 右侧元素小，统计逆序对
tmp[i++] = nums[cur2++];
}
}
// 4. 处理剩余元素
while (cur1 <= mid) tmp[i++] = nums[cur1++];
while (cur2 <= right) tmp[i++] = nums[cur2++];
// 5. 将 tmp 数组内容拷贝回原数组
for (int j = left; j <= right; j++) {
nums[j] = tmp[j - left];
}
return ret;
}
};
left >= right 时，表示已将数组分割到单个元素，递归停止返回 0。nums[cur1] > nums[cur2] 时，说明 left[cur1] 及后面的所有元素都大于 right[cur2]，则这些元素与 right[cur2] 构成逆序对。统计并更新 ret 的值。tmp，因为剩余部分不会形成逆序对。tmp 的排序结果拷贝回 nums，确保在递归的上一级合并时数组依旧有序。O(n log n)。归并排序的分治递归实现使得时间复杂度达到 O(n log n)。O(n)，需要额外的数组存储合并结果。题目链接：315. 计算右侧小于当前元素的个数
题目描述：
给你一个整数数组 nums，按要求返回一个新数组 counts。
数组 counts 有如下性质：counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例 1：
nums = [5,2,6,1][2,1,1,0]解释：
算法思路：
本题和求数组中的逆序对非常类似，但与逆序对的统计不同之处在于：
counts，记录每个元素右侧更小的元素数量，而不是单一的逆序对总数。index 数组，用于记录元素对应的原始索引，确保元素与下标绑定在一起。ret 数组存储每个元素右侧更小元素的数量。ret 索引上。class Solution {
vector<int> ret; // 结果数组
vector<int> index; // 记录元素的原始下标
int tmpNums[100010]; // 临时数组用于排序
int tmpIndex[100010]; // 临时数组用于记录索引排序
public:
vector<int> countSmaller(vector<int>& nums) {
int n = nums.size();
ret.resize(n, 0); // 初始化结果数组为 0
index.resize(n); // 初始化下标数组
for (int i = 0; i < n; i++) {
index[i] = i; // 初始时，索引与数组位置一一对应
}
mergeSort(nums, 0, n - 1);
return ret;
}
void mergeSort(vector<int>& nums, int left, int right) {
if (left >= right) return;
// 1. 分区
int mid = (left + right) / 2;
// 2. 递归处理左右子区间
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
// 3. 合并并统计逆序对
int cur1 = left, cur2 = mid + 1, i = 0;
while (cur1 <= mid && cur2 <= right) {
if (nums[cur1] <= nums[cur2]) {
tmpNums[i] = nums[cur2];
tmpIndex[i++] = index[cur2++];
} else {
// 当前左侧元素大于右侧元素，统计逆序对
ret[index[cur1]] += right - cur2 + 1;
tmpNums[i] = nums[cur1];
tmpIndex[i++] = index[cur1++];
}
}
// 处理剩余元素
while (cur1 <= mid) {
tmpNums[i] = nums[cur1];
tmpIndex[i++] = index[cur1++];
}
while (cur2 <= right) {
tmpNums[i] = nums[cur2];
tmpIndex[i++] = index[cur2++];
}
// 拷贝回原数组
for (int j = left; j <= right; j++) {
nums[j] = tmpNums[j - left];
index[j] = tmpIndex[j - left];
}
}
};
index 也需要同步排序，以保证结果数组 ret 的统计准确。nums[cur1] > nums[cur2] 时，说明从 cur2 到 right 的所有元素都小于 nums[cur1]，需要将这些数量累加到 ret[index[cur1]]。left >= right 时停止递归，避免无效操作。O(n log n)。分治递归的时间复杂度是 O(log n)，每次合并的时间复杂度是 O(n)。O(n)。需要额外的临时数组 tmpNums 和 tmpIndex 进行合并排序。题目链接：493. 翻转对
题目描述：
给定一个数组 nums，如果 i < j 且 nums[i] > 2 * nums[j]，我们就将 (i, j) 称作一个重要翻转对。
你需要返回给定数组中的重要翻转对的数量。
示例 1：
nums = [1,3,2,3,1]2算法思路：
翻转对的统计与逆序对非常类似，都可以利用 归并排序 的思想，将问题分解为三部分：
由于翻转对要求的是 nums[i] > 2 * nums[j]，直接在合并排序时统计会比较困难，因此：
cur1 和 cur2，分别遍历左、右子数组。nums[cur1]，找到右数组中第一个不满足 nums[cur1] > 2 * nums[cur2] 的位置 cur2。cur2 - mid - 1 即为当前 cur1 的翻转对数量，累加到结果中。[left, mid] 和 [mid + 1, right]，递归统计翻转对数量并排序。class Solution {
int tmp[50010]; // 临时数组用于合并排序
public:
int reversePairs(vector<int>& nums) {
return mergeSort(nums, 0, nums.size() - 1);
}
int mergeSort(vector<int>& nums, int left, int right) {
if (left >= right) return 0;
int ret = 0;
// 1. 分区
int mid = (left + right) / 2;
// 2. 递归计算左右区间的翻转对数量
ret += mergeSort(nums, left, mid);
ret += mergeSort(nums, mid + 1, right);
// 3. 统计翻转对数量
int cur1 = left, cur2 = mid + 1;
while (cur1 <= mid) {
while (cur2 <= right && nums[cur2] * 2 < nums[cur1]) {
cur2++;
}
ret += cur2 - mid - 1;
cur1++;
}
// 4. 合并两个有序数组
cur1 = left, cur2 = mid + 1;
int i = left;
while (cur1 <= mid && cur2 <= right) {
tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
}
while (cur1 <= mid) tmp[i++] = nums[cur1++];
while (cur2 <= right) tmp[i++] = nums[cur2++];
for (int j = left; j <= right; j++) {
nums[j] = tmp[j];
}
return ret;
}
};
cur2 指针只向右移动，不会回退，避免重复计算。nums[cur1] > 2 * nums[cur2]，需要考虑到浮点运算可能导致的精度问题，因此 2 * nums[cur2] 可能需要写成 nums[cur1] > 2LL * nums[cur2]。left >= right。O(n log n)。
log n，每层递归需要合并排序和统计翻转对，复杂度为 O(n)。O(n)。
tmp 进行排序。通过以上方法，翻转对的数量可以在 O(n log n) 的时间复杂度内高效统计。
在本次归并排序专题中，我们以经典的分治思想为核心，逐层剖析了归并排序的精髓及其在算法中的高级应用。从数组排序到统计逆序对，再到复杂的翻转对和右侧更小元素计数，归并排序不仅是解决基础问题的利器，更是攻克高阶难题的关键。我们以逐步深入的方式，从基础实现到优化分析，贯穿了分治思想的深度与广度。
分治法的核心在于'分而治之'，通过不断将大问题拆解为小问题，并利用递归与合并的方式重新组合结果。在归并排序中，借助临时数组和指针操作，我们能够高效完成排序，并在此过程中完成复杂的统计任务。它不仅展现了算法的美学，更体现了计算机科学中化繁为简的哲学。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online