归并排序与数组逆序对问题详解

流程解析

合并阶段是归并排序的关键。我们需要一个临时数组 tmp 来暂存合并结果，避免原地交换带来的复杂逻辑。当左右指针指向的元素比较时，较小的元素先放入 tmp。若一边遍历完另一边还有剩余，直接拷贝即可。最后将 tmp 中的数据复制回原数组对应位置。

48. 数组中的逆序对

题目描述

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

解法思路

利用归并排序的过程统计逆序对数量是非常经典的做法。归并排序本身就在不断合并两个有序序列，我们可以在合并的过程中顺便计算逆序对。

假设我们将数组从中间划分为左半部分和右半部分，逆序对可以分为三类：

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

前两类可以通过递归解决，第三类需要在合并过程中统计。关键在于：当左半部分的当前元素大于右半部分的当前元素时，左半部分该元素及其之后的所有元素都与右半部分当前元素构成逆序对。

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];
        }
    }
};

总结

归并排序采用分治思想，先将数组不断二分至单个元素，再通过有序合并操作完成排序，时间复杂度为 O(nlogn)。在合并两个有序数组时，利用双指针特性可以快速统计出跨越左右两部分的逆序对数量，无需额外枚举。这种方法既完成了排序任务，又高效解决了逆序对计数问题。