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

算法流程解析

48. 数组中的逆序对

题目链接

LCR 170. 交易逆序对的总数 - 力扣（LeetCode）

题目描述

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

解题思路

暴力枚举的时间复杂度是 O(n²)，对于大数据量会超时。利用归并排序的过程来统计逆序对是经典解法。

为什么可以用归并排序？

当我们把数组从中间切开时，逆序对只可能出现在三种情况：

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

前两种情况可以通过递归解决，第三种情况则可以在「合并」两个有序子数组时高效统计。

如何在合并时统计？

假设我们有两个已排序的子数组 Left 和 Right。使用双指针 cur1 和 cur2 分别指向它们的头部。

• 如果 nums[cur1] <= nums[cur2]：说明当前左边的元素不大于右边的元素，不构成逆序对，直接放入临时数组。
• 如果 nums[cur1] > nums[cur2]：关键点来了。因为左边数组是有序的，既然 nums[cur1] 已经大于 nums[cur2]，那么 nums[cur1] 后面的所有元素（即 mid - cur1 + 1 个）也都大于 nums[cur2]。这 mid - cur1 + 1 个元素都与 nums[cur2] 构成了逆序对。

这样我们就不需要逐个比较，而是批量累加计数，将复杂度降到了 O(n log n)。

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)。在合并过程中巧妙利用有序性统计逆序对，避免了暴力枚举的高开销。