分治归并排序核心原理及 LeetCode 实战

概念解析

分治归并（基于分治思想的归并排序）是分治算法在排序问题中的经典应用。核心思路是通过'拆分 - 排序 - 合并'三步，将无序数组转化为有序数组，本质是化繁为简、再合简为繁的解题策略。

基础：排序数组

题目描述：

示例：

题目链接： LeetCode 912. 排序数组

实现思路：

本质上分治归并就是一个后序遍历的过程。快排是前序遍历，而归并则是不断向下细分数组，然后从下往上把左右两分支的数组排序并合并，以此向上循环往复。

代码实现：

#include <iostream>
#include <vector>
using namespace std;

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;
        int mid = left + ((right - left) >> 1);
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        
        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++];
        
        for (int j = 0; j <= right - left; ++j) {
            nums[left + j] = tmp[j];
        }
    }
};

细节注意：

• mid 计算使用 left + ((right - left) >> 1) 而非 (left + right) / 2，这是为了避免整数溢出，同时位运算效率略高。
• 最后一步合并回原数组时，赋值目标是 nums[left + j] 而不是 nums[j]，因为递归过程中 left 不一定为 0，我们可能只在对数组的一部分进行排序。
• 数组排序本身不影响逆序对的计算逻辑，因为逆序对统计是在左右两部分比较时完成的，内部递归已经处理了子区间。

进阶：交易逆序对的总数

题目描述：

示例：

题目链接： 剑指 Offer 51. 数组中的逆序对

实现思路：

归并排序的'分治 + 有序合并'特性完美匹配逆序对统计的核心需求。暴力枚举无法应对大数据量，而归并可以在 $O(n \log n)$ 时间内完成。

当 [left, mid] 和 [mid+1, right] 进行互相比较时，如果当前处于升序状态，且发现 record[cur1] >= record[cur2]，由于左半部分已有序，所以 cur2 之后的所有元素都小于 record[cur1]。这意味着我们可以直接批量计算出一批逆序数对，无需逐个比对。

代码实现：

class Solution {
    vector<int> tmp;
public:
    int reversePairs(vector<int>& record) {
        tmp.resize(50010);
        return mergeSort(record, 0, record.size() - 1);
    }

    int mergeSort(vector<int>& record, int left, int right) {
        if (left >= right) return 0;
        int ret = 0;
        int mid = left + ((right - left) >> 1);
        ret += mergeSort(record, left, mid);
        ret += mergeSort(record, mid + 1, right);
        
        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= right) {
            if (record[cur1] <= record[cur2]) {
                tmp[i++] = record[cur1++];
            } else {
                ret += mid - cur1 + 1;
                tmp[i++] = record[cur2++];
            }
        }
        while (cur1 <= mid) tmp[i++] = record[cur1++];
        while (cur2 <= right) tmp[i++] = record[cur2++];
        
        for (int j = 0; j < right - left + 1; ++j) {
            record[j + left] = tmp[j];
        }
        return ret;
    }
};

扩展：计算右侧小于当前元素的个数

题目描述：

示例：

题目链接： LeetCode 315. 计算右侧小于当前元素的个数

实现思路：

这题和上一题思路基本一致，唯一的难点在于题目要求返回每个 index 对应的值。有人可能会问为什么不用哈希表？可以是可以，但如果有重复值会很麻烦。因此额外创建一个数组进行 index 和值的绑定更方便，index 数组跟着 nums 数组一起移动即可。

代码实现：

class Solution {
    vector<int> ret;
    vector<int> index;
    int tmpNums[500010];
    int tmpIndex[500010];
public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        ret.resize(n, 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;
        int mid = left + ((right - left) >> 1);
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        
        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= right) {
            if (nums[cur1] <= nums[cur2]) {
                tmpNums[i] = nums[cur1];
                tmpIndex[i++] = index[cur1++];
            } else {
                ret[index[cur1]] += right - cur2 + 1;
                tmpNums[i] = nums[cur2];
                tmpIndex[i++] = index[cur2++];
            }
        }
        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 = 0; j < right - left + 1; ++j) {
            nums[j + left] = tmpNums[j];
            index[j + left] = tmpIndex[j];
        }
    }
};

变体：翻转对

题目描述：

示例：

题目链接： LeetCode 493. 翻转对

实现思路：

思路依然是利用归并解决，但要提前计算符合题目要求的翻转对。如果在排序过程中直接计算，会漏掉部分翻转对，因为排序会打乱原始相对位置。我们需要在归并排序的合并阶段之前，先统计满足条件的对数。

代码实现：

class Solution {
    vector<int> tmp;
    int ret = 0;
public:
    int reversePairs(vector<int>& nums) {
        tmp.resize(nums.size());
        mergeSort(nums, 0, nums.size() - 1);
        return ret;
    }

    void mergeSort(vector<int>& nums, int left, int right) {
        if (left >= right) return;
        int mid = left + ((right - left) >> 1);
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        
        // 先统计翻转对，此时左右两边各自有序
        int cur1 = left, cur2 = mid + 1;
        while (cur2 <= right) {
            while (cur1 <= mid && (long long)nums[cur1] <= 2LL * nums[cur2]) {
                cur1++;
            }
            if (cur1 > mid) break;
            ret += mid - cur1 + 1;
            cur2++;
        }
        
        // 再进行正常的归并排序
        cur1 = left, cur2 = mid + 1;
        int i = 0;
        while (cur1 <= mid && cur2 <= right) {
            if (nums[cur1] <= nums[cur2]) {
                tmp[i++] = nums[cur1++];
            } else {
                tmp[i++] = nums[cur2++];
            }
        }
        while (cur1 <= mid) tmp[i++] = nums[cur1++];
        while (cur2 <= right) tmp[i++] = nums[cur2++];
        
        for (int j = 0; j < right - left + 1; ++j) {
            nums[j + left] = tmp[j];
        }
    }
};

细节注意：

• 判断条件 (long long)nums[cur1] <= 2LL * nums[cur2] 必须强制转换类型，防止乘法溢出。
• 统计翻转对和归并排序是两个独立的步骤，顺序不能颠倒。