归并排序与数组逆序对：分治算法实战解析

流程解析

合并过程中使用双指针分别指向左右两个有序区间的起始位置。比较指针所指元素，将较小者放入临时数组，并移动对应指针。当某一侧遍历完后，直接将另一侧剩余元素拷贝过去。最后将临时数组的数据复制回原数组对应区间。

48. 数组中的逆序对

题目链接

• LCR 170. 交易逆序对的总数 - LeetCode

题目描述

在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请计算给定数组中所有逆序对的总数。

题目示例

输入：[7, 5, 6, 4] 输出：5 解释：(7,5), (7,6), (7,4), (5,4), (6,4)

解法：利用归并排序统计

算法思路

暴力枚举的时间复杂度为 O(n^2)，无法通过大规模数据测试。利用归并排序的特性可以在 O(nlogn) 时间内解决。

核心逻辑： 逆序对可以分为三类：

1. 两个元素都在左半部分。
2. 两个元素都在右半部分。
3. 一个在左半部分，一个在右半部分。

前两类可以通过递归解决。第三类是关键：在归并排序的合并阶段，当我们将两个有序数组合并时，如果发现右半部分的某个元素小于左半部分的当前元素，那么左半部分该元素及其之后的所有元素都与右半部分该元素构成逆序对。

例如：左 [3, 5]，右 [2, 4]。当比较到 3 和 2 时，因为 3 > 2，所以 3 和 5 都比 2 大，贡献了 2 个逆序对。

C++ 算法代码

class Solution {
public:
    int count = 0;
    vector<int> tmp;

    int reversePairs(vector<int>& record) {
        tmp.resize(record.size());
        mergesort(record, 0, record.size() - 1);
        return count;
    }

    void mergesort(vector<int>& nums, int left, int right) {
        if (left >= right) return;

        int mid = (right - left) / 2 + left;
        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 {
                // 关键：左半部分当前元素大于右半部分元素
                // 说明左半部分从 cur1 到 mid 的所有元素都大于 nums[cur2]
                count += 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];
        }
    }
};

总结

归并排序不仅用于排序，其合并过程天然适合统计跨区间的顺序关系。通过修改合并逻辑，即可高效计算逆序对数量。注意处理空数组等边界情况，确保递归终止条件正确。