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

流程解析

48. 数组中的逆序对

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

解法思路

暴力枚举的时间复杂度是 O(n²)，对于大数据量会超时。利用归并排序的合并过程可以在 O(nlogn) 内解决。

为什么能用归并排序？

逆序对可以分为三类：

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

前两类可以通过递归解决，第三类需要在合并时统计。归并排序天然具备'先排好左右，再合并'的特性，非常适合处理此类问题。

核心逻辑：如何在合并时统计？

当合并两个有序数组时，假设当前指针分别为 cur1（左半区）和 cur2（右半区）。

• 如果 nums[cur1] <= nums[cur2]：说明左边的数较小，不构成逆序对，直接放入临时数组。
• 如果 nums[cur1] > nums[cur2]：关键点来了。因为左半区本身是有序的，既然 nums[cur1] 已经比 nums[cur2] 大了，那么 nums[cur1] 及其之后的所有元素（即 [cur1, mid] 区间）也都比 nums[cur2] 大。
• 因此，此时产生的逆序对数量 += mid - cur1 + 1。

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 {
                // 发现逆序对：左半区剩余元素均大于右半区当前元素
                count += mid - cur1 + 1;
                tmp[i++] = nums[cur2++];
            }
        }

        while (cur1 <= mid) tmp[i++] = nums[cur1++];
        while (cur2 <= right) tmp[i++] = nums[cur2++];

        for (int i = left; i <= right; i++) {
            nums[i] = tmp[i - left];
        }
    }
};

流程解析