在算法面试中，“数组中的逆序对”是考察分治思想与排序算法应用的经典题目。其核心挑战在于如何在大规模数据下（如size<=2*10^5）高效统计逆序对数量，避免暴力解法的时间瓶颈。本文将从问题本质出发，拆解两种核心解法，深入剖析归并排序在该问题中的优化逻辑，并提供可直接运行的多语言代码，结合实例验证效果，帮助读者掌握分治思想的实际应用。

一、问题定义：什么是逆序对？

1. 概念描述

根据《剑指Offer》题目定义：
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。例如数组{7,5,6,4}中，逆序对为(7,5)、(7,6)、(7,4)、(5,4)、(6,4)，共5对。

2. 题目要求

• 输入：一个无重复元素的整数数组；
• 输出：逆序对总数P对1000000007（即10^9+7）取模的结果；
• 数据范围：
• 基础用例（50%）：数组长度<=10^4；
• 中等用例（75%）：数组长度<=10^5；
• 进阶用例（100%）：数组长度<=2*10^5。

3. 示例

• 输入：[1,2,3,4,5,6,7,0]
• 输出：7（逆序对为(1,0)、(2,0)、...、(7,0)，共7对）。

二、解法一：暴力解法（直观但低效）

1. 思路逻辑

暴力解法的核心是“逐个比对”：

1. 遍历数组中的每个元素data[i]（i从0到n-2）；
2. 对于每个data[i]，遍历其后面所有元素data[j]（j从i+1到n-1）；
3. 若data[i] > data[j]，则计数count +=1；
4. 最终返回count % 1000000007。

2. 代码实现（Python）

# -*- coding:utf-8 -*-
class Solution:
    def InversePairs(self, data):
        if not data:
            return 0
        n = len(data)
        count = 0
        # 外层遍历每个元素
        for i in range(n - 1):
            # 内层遍历当前元素后面的所有元素
            for j in range(i + 1, n):
                if data[i] > data[j]:
                    count += 1
        # 取模返回
        return count % 1000000007

3. 复杂度分析

维度 分析结果 问题所在 时间复杂度 O(n^2) 对于n=2*10^5，n^2=4*10^10次操作，远超时间限制（通常算法允许10^8次操作/秒），必然超时； 空间复杂度 O(1) 仅用常量额外空间，无问题； 适用场景 小规模数组（n<=10^3） 无法满足题目进阶用例需求；

结论：暴力解法仅适用于理解问题，实际面试或工程中需优化。

三、解法二：归并排序+分治（高效最优解）

1. 核心思想：分治与归并的结合

逆序对的总数可拆分为三部分：

• 左半段内部的逆序对数量；
• 右半段内部的逆序对数量；
• 左半段元素与右半段元素组成的逆序对数量（跨区间逆序对）。

这恰好符合分治思想的“分解-求解-合并”逻辑，而归并排序的“合并有序子数组”过程，可天然统计跨区间逆序对——因为合并前左、右子数组已各自有序，无需重复统计子数组内部的逆序对。

2. 原理拆解（三步曲）

以数组{7,5,6,4}为例，演示完整过程：

步骤1：分解（Divide）

将数组递归拆分为长度为1的子数组（不可再分）：
{7,5,6,4} → {7,5} 和 {6,4} → {7}、{5} 和 {6}、{4}。

步骤2：求解子问题（Conquer）

递归统计每个子数组内部的逆序对：

• 子数组{7}和{5}：合并前统计内部逆序对(7,5)，计数1；
• 子数组{6}和{4}：合并前统计内部逆序对(6,4)，计数1；
• 左半段总逆序对leftCount=1，右半段总逆序对rightCount=1。

步骤3：合并与统计跨区间逆序对（Merge）

合并两个有序子数组时，统计左半段元素大于右半段元素的情况（跨区间逆序对）：
以合并{5,7}（左）和{4,6}（右）为例：

1. 初始化指针：左子数组末尾i=1（值7）、右子数组末尾j=1（值6）、辅助数组指针index=3；
2. 比较7>6：说明左子数组的7与右子数组剩余元素[4,6]都构成逆序对，计数count += j - mid（mid=1，j=1，即1-1+1=2？此处需结合代码逻辑修正：实际mid是左子数组的右边界，右子数组从mid+1开始，故右子数组当前长度为j - mid）；
3. 将7存入辅助数组，i--；
4. 继续比较5>6？不，将6存入辅助数组，j--；
5. 比较5>4：计数count += j - mid（j=0，0-1+1=1），将5存入辅助数组，i--；
6. 剩余元素4存入辅助数组；
7. 跨区间逆序对count=2+1=3。

最终总逆序对：leftCount + rightCount + count = 1+1+3=5，与示例一致。

3. 关键逻辑：如何高效统计跨区间逆序对？

核心在于利用子数组的有序性，避免逐个比对：
假设左子数组L（有序）和右子数组R（有序），从末尾向前遍历（或从前往后，逻辑等价）：

• 若L[i] > R[j]：则L[i]与R[j]、R[j-1]、...、R[mid+1]（右子数组剩余所有元素）均构成逆序对，数量为j - mid（mid是L的右边界）；
• 若L[i] <= R[j]：无逆序对，直接将R[j]存入辅助数组；
• 最后将剩余元素（L或R中未处理的）存入辅助数组，保证辅助数组有序。

4. 代码实现（C++与Python）

4.1 C++实现（从后向前合并）

#include <vector>
using namespace std;

class Solution {
public:
    int InversePairs(vector<int> data) {
        // 边界处理：空数组返回0
        if (data.size() == 0) {
            return 0;
        }
        // 辅助数组：用于存储合并后的有序结果，避免原数组被覆盖
        vector<int> copy;
        for (int i = 0; i < data.size(); ++i) {
            copy.push_back(data[i]);
        }
        // 调用核心递归函数，最终结果取模1e9+7
        return InversePairsCore(data, copy, 0, data.size() - 1) % 1000000007;
    }

private:
    // 核心递归函数：将data[begin..end]合并排序后存入copy[begin..end]，并返回该区间逆序对总数
    long InversePairsCore(vector<int>& data, vector<int>& copy, int begin, int end) {
        // 终止条件：单个元素无逆序对，直接复制到辅助数组
        if (begin == end) {
            copy[begin] = data[end];
            return 0;
        }
        // 求中点（右移1位等价于除以2，效率更高）
        int mid = (begin + end) >> 1;
        
        // 递归处理左半段：注意参数交换（data为数据源，copy为目标数组）
        long leftCount = InversePairsCore(copy, data, begin, mid);
        // 递归处理右半段
        long rightCount = InversePairsCore(copy, data, mid + 1, end);
        
        // 统计跨区间逆序对
        int i = mid;          // 左子数组末尾指针
        int j = end;          // 右子数组末尾指针
        int indexCopy = end;  // 辅助数组末尾指针
        long crossCount = 0;  // 跨区间逆序对计数（用long防溢出）
        
        // 从后向前合并两个有序子数组
        while (i >= begin && j >= mid + 1) {
            if (data[i] > data[j]) {
                // 左元素大于右元素：统计逆序对（右子数组剩余长度 = j - mid）
                copy[indexCopy--] = data[i--];
                crossCount += j - mid;
                // 可选：提前取模，防止crossCount过大（题目要求最终取模，此处可省略）
                // crossCount %= 1000000007;
            } else {
                // 左元素小于等于右元素：无逆序对
                copy[indexCopy--] = data[j--];
            }
        }
        
        // 处理左子数组剩余元素
        while (i >= begin) {
            copy[indexCopy--] = data[i--];
        }
        // 处理右子数组剩余元素
        while (j >= mid + 1) {
            copy[indexCopy--] = data[j--];
        }
        
        // 返回总逆序对（左+右+跨区间）
        return leftCount + rightCount + crossCount;
    }
};

4.2 Python实现（从前往后合并）

Python版本采用“从前往后”合并逻辑，核心统计逻辑一致，需注意整数整除和参数交换：

# -*- coding:utf-8 -*-
class Solution:
    def InversePairs(self, data):
        # 边界处理：空数组返回0
        if not data:
            return 0
        # 辅助数组：复制原数组，用于存储排序结果
        temp = data.copy()
        # 调用归并排序函数，最终结果取模1e9+7
        return self.merge_sort(temp, data, 0, len(data)-1) % 1000000007
    
    def merge_sort(self, temp, data, low, high):
        # 终止条件：单个元素无逆序对，复制到目标数组
        if low >= high:
            temp[low] = data[low]
            return 0
        
        # 求中点（Python3需用//保证整数，避免浮点数索引）
        mid = (low + high) // 2
        
        # 递归处理左半段：参数交换（data为源，temp为目标）
        left_count = self.merge_sort(data, temp, low, mid)
        # 递归处理右半段
        right_count = self.merge_sort(data, temp, mid+1, high)
        
        # 统计跨区间逆序对
        cross_count = 0
        i = low          # 左子数组起始指针
        j = mid + 1      # 右子数组起始指针
        index = low      # 辅助数组起始指针
        
        # 从前往后合并两个有序子数组
        while i <= mid and j <= high:
            if data[i] <= data[j]:
                # 左元素小：无逆序对，存入辅助数组
                temp[index] = data[i]
                i += 1
            else:
                # 左元素大：统计逆序对（左子数组剩余元素数 = mid - i + 1）
                temp[index] = data[j]
                cross_count += mid - i + 1
                j += 1
            index += 1
        
        # 处理左子数组剩余元素
        while i <= mid:
            temp[index] = data[i]
            i += 1
            index += 1
        # 处理右子数组剩余元素
        while j <= high:
            temp[index] = data[j]
            j += 1
            index += 1
        
        # 返回总逆序对
        return left_count + right_count + cross_count

5. 复杂度分析

维度 分析结果 优势 时间复杂度 O(nlogn) 归并排序的时间复杂度，n=2*10^5时nlogn≈2*10^5*18=3.6*10^6次操作，远低于时间限制； 空间复杂度 O(n) 需辅助数组存储排序结果，空间开销可接受； 适用场景 大规模数组（n<=2*10^5） 完全满足题目所有用例需求；

四、两种解法对比与关键注意事项

1. 解法对比表

对比维度 暴力解法 归并排序分治解法 时间复杂度 O(n^2) O(nlogn) 空间复杂度 O(1) O(n) 适用数据规模 小规模（n<=10^3） 大规模（n<=2*10^5） 核心优势 逻辑直观、无额外空间 高效、可扩展 核心劣势 超时风险高 需辅助数组、递归逻辑较复杂

2. 关键注意事项

1. 数据溢出问题：
   逆序对总数可能极大（如n=2*10^5时，最大逆序对数量为2*10^5*(2*10^5-1)/2≈2*10^10），远超int类型范围（C++中int约2*10^9）。因此需用long（C++）或Python原生整数（无溢出限制）存储计数，最终取模1000000007。
2. 辅助数组的参数交换：
   归并排序中，data和copy的角色需交替：递归时将data作为数据源，copy作为目标数组存储排序结果；下次递归时，再以copy为数据源，data为目标数组。这是为了避免覆盖未处理的原数据，保证递归逻辑正确。
3. 递归深度问题：
   归并排序的递归深度为log2(n)，n=2*10^5时递归深度仅18，远低于C++和Python的默认递归栈深度（通常为1000以上），无需担心栈溢出。

五、总结

“数组中的逆序对”问题的核心是将统计逆序对与排序算法结合，通过归并排序的分治思想，将原本O(n^2)的问题优化为O(nlogn)。这种“以排序换效率”的思路，不仅是解决逆序对问题的最优解，还可迁移到类似问题中（如“统计数组中每个元素后面比它小的元素个数”“区间逆序对查询”等）。

对于程序员而言，掌握该解法的关键在于：

1. 理解逆序对的“三分法”拆分（左、右、跨区间）；
2. 掌握归并排序合并过程中统计跨区间逆序对的逻辑；
3. 注意数据溢出、辅助数组使用等细节问题。

通过本文的原理拆解与代码实现，相信读者能深入理解分治思想的实际应用，在面对类似算法问题时，能快速想到“排序+统计”的优化方向。