【优选算法篇】归并排序模型——从基础排序到逆序对统计

Trouvaille ~

365人浏览 · 2026-03-20 11:20:21

Trouvaille ~ · 2026-03-20 11:20:21 发布

文章目录

分治的艺术：合并过程中的信息收割

一、前言：归并排序的隐藏价值

💬 开篇：很多初学者认为归并排序只是为了排序。其实，归并排序最核心的价值在于其 “合并（Merge）”阶段。

🚀 核心破局点：
在合并两个子数组时，我们可以通过简单的指针移动，成批地统计出跨越左右区间的元素关系。这种“成批统计”将原本 $O(N^2)$ 的暴力统计降维到了 $\log N)$ 。

👍 学习：本篇的重点在于 “逆序对”和“翻转对” 的数学推导。掌握了“升序”和“降序”两种版本的统计逻辑，你就能在面试中对这类 Hard 题降维打击。

二、归并排序基础：分而治之 (Medium)

2.1 题目描述

题目链接：912. 排序数组

描述：升序排列数组。

2.2 算法流程

分（Divide）：取中点 mid，递归排序左半部分和右半部分。
治（Conquer/Merge）：双指针遍历两个有序数组，谁小谁放入辅助数组 tmp。
还原：将 tmp 中的有序序列拷贝回原数组。

2.3 C++ 代码实战

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) >> 1;

        // 2. 递归排序
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        // 3. 合并有序数组 (治)
        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++];

        // 4. 还原回原数组
        for (int j = left; j <= right; j++) {
            nums[j] = tmp[j - left];
        }
    }
};

三、数组中的逆序对：合并中的“成批处理” (Hard)

3.1 题目描述

题目链接：LCR 170. 交易逆序对的总数（原：数组中的逆序对）

描述：若 $i < j$ 且 $n u m s [i] > n u m s [j]$ ，则构成一个逆序对。求总数。

3.2 深度拆解：为什么归并能求逆序对？

我们将逆序对分为三类：

左半区内部的逆序对：递归解决。
右半区内部的逆序对：递归解决。
一左一右跨区间的逆序对：在合并过程中统计。

核心贪略（升序归并版本）：
合并时，如果 nums[cur1] > nums[cur2]：

- 证明：因为左半区是有序的，既然 nums[cur1] 比 nums[cur2] 大，那么从 cur1 到 mid 的所有元素都一定比 nums[cur2] 大！
结论：这些元素都能与 numscur2]构成逆序对。数量直接累加mid - cur1 + 1，无需一个个去数。

3.3 C++ 代码实战

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 mid = (left + right) >> 1;
        // 分治：左边对数 + 右边对数
        int ret = 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]) {
                tmp[i++] = nums[cur1++];
            } else {
                // 此时 nums[cur1...mid] 全部大于 nums[cur2]
                ret += (mid - cur1 + 1); // 成批统计！
                tmp[i++] = 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 - left];

        return ret;
    }
};

四、计算右侧小于当前元素的个数：索引绑定的艺术 (Hard)

4.1 题目描述

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

描述：返回新数组 counts，其中 counts[i] 是 nums[i] 右侧小于它的元素数量。

4.2 深度拆解：坐标绑定的降序归并

这题比上一题更难：它不是要总数，而是要每个元素各自的对数。
但归并排序会打乱元素的原始下标，怎么办？

破局点：

索引数组 index：我们不直接搬运 nums，我们搬运它们的下标。通过 nums[index[i]] 访问数值，这样排序后我们依然知道它是谁。
降序归并（更直观）：如果我们按降序排列：
- 当 nums[index[cur1]]> nums[index[cur2]] 时：
- 证明：右半区 cur2 到 right 的元素都一定比 nums[index[cur1]] 小！
- 结论：将这个数量 right - cur2+ 1累加到ret[index[cur1]] 中。

4.3 C++ 代码实战

class Solution {
    vector<int> ret;
    vector<int> index; // 记录原始下标
    int tmpNums[500010], 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) >> 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[index[cur1]] <= nums[index[cur2]]) {
                tmpIndex[i++] = index[cur2++];
            } else {
                // nums[index[cur1]] 大于右边 [cur2...right] 的所有数
                ret[index[cur1]] += (right - cur2 + 1);
                tmpIndex[i++] = index[cur1++];
            }
        }
        while (cur1 <= mid) tmpIndex[i++] = index[cur1++];
        while (cur2 <= right) tmpIndex[i++] = index[cur2++];
        for (int j = left; j <= right; j++) index[j] = tmpIndex[j - left];
    }
};

五、翻转对：统计与归并的解耦 (Hard)

5.1 题目描述

题目链接：493. 翻转对

描述：若 $i < j$ 且 $n u m s [i] > 2 * n u m s [j]$ ，求翻转对总数。

5.2 核心逻辑：先统计，再归并

为什么这题不能边合并边统计？
因为逆序对的关系是 $a > b$ ，和排序的比较逻辑一致。
而翻转对的关系是 $a > 2 b$ ，这和排序的比较逻辑不一致！
强行在合并过程中统计会导致指针逻辑极其混乱。

贪心策略（解耦）：

先利用左右两块已有序的特性独开启循环统计跨区间的翻转对。
指针 cur1 在左，cur2 在右。对于每个 cur1，移动 cur2 直到不满足条件。因为是递增的，cur2 不需要回退。
统计完后，再执行常规的归并排序过程。

5.3 C++ 代码实战

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 mid = (left + right) >> 1;
        int ret = mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right);

        // 1. 单独统计翻转对 (i < j && nums[i] > 2 * nums[j])
        int i = left, j = mid + 1;
        while (i <= mid) {
            // 利用 double 避免乘法溢出，或者用 long long
            while (j <= right && nums[i] > 2.0 * nums[j]) j++;
            ret += (j - (mid + 1));
            i++;
        }

        // 2. 常规归并排序合并
        int cur1 = left, cur2 = mid + 1, k = 0;
        while (cur1 <= mid && cur2 <= right)
            tmp[k++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        while (cur1 <= mid) tmp[k++] = nums[cur1++];
        while (cur2 <= right) tmp[k++] = nums[cur2++];
        for (int p = left; p <= right; p++) nums[p] = tmp[p - left];

        return ret;
    }
};