求逆序对数：从双重循环到归并顺带统计

本文属于「408 算法拓展训练」——考纲内、真题代码题尚未考过的经典题。归并排序是「排序」这一章的核心算法之一，考纲要求掌握它的分治过程和复杂度分析，而「顺带统计逆序对」是归并排序最经典的扩展应用，能检验对 merge 过程的理解是否到位。它是经典训练题，不是真题，也不押题。

题目

给定一个含 n 个整数的数组 a，如果存在 i < j 且 a[i] > a[j]，则称 (i, j) 是一个逆序对。设计一个时间上尽可能高效的算法，求出数组中逆序对的总数。

题面出现了「尽可能高效」，按拓展训练导语的分类，这道题属于「暴力→最优」型。

第一步：把暴力解写对——双重循环枚举

最直接的想法：枚举所有满足 i < j 的下标对，逐一检查 a[i] 是否大于 a[j]，是就计数加一。

long long countInversionsBrute(int a[], int n) {
    long long count = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (a[i] > a[j]) count++;
    return count;
}

拿 a = [2,4,1,3,5] 走一遍：(0,2) 处 2>1、(1,2) 处 4>1、(1,3) 处 4>3，一共 3 对逆序，其余组合都满足 a[i] <= a[j]。

复杂度：双重循环枚举所有 $(\binom{n}{2})$ 对下标，时间 $O (n^{2})$ ；只用了一个计数变量，空间 $O (1)$ 。

它值多少分

用总纲的两维度看：

正确性：双重循环枚举了所有满足 i<j 的下标对，逐对比较，结果一定正确，复杂度分析 $O (n^{2})$ 与实现一致。正确性维度的分拿得到。
最优性：题面要求「尽可能高效」，期望复杂度是 $O (n \log n)$ 。暴力解的 $O (n^{2})$ 达不到，这一档拿不到。

暴力解的浪费在哪

用总纲的「找浪费三问」审一遍：

有没有重复扫描？——有，而且是逐对比较本身就带着浪费。 暴力解对每一对 (i, j) 都单独判一次大小，但如果 a[i..j] 这一段能分成两个已经排好序的半区，那么「这半区里有多少个数比另一半区的某个数大」这件事，其实可以一次性批量算出来，不需要再退回到「一个一个比」的粒度。

具体一点：假设数组被拆成左右两个已经各自排好序的半区。合并这两个半区时，如果右半区的某个数 x 比左半区剩余的第一个数还小，那么它一定比左半区剩余的所有数都小（因为左半区是有序的）——这意味着 x 和左半区剩余的每一个数都构成一个逆序对，这些逆序对可以一次性数出个数，不需要把它们一对一对拆开来比。

浪费的本质：暴力解把每一对逆序单独判一次，而「两个有序半区合并」这个过程，本可以把一大批逆序对一次性数清楚。

智慧化改造：归并排序顺带统计

对策是总纲里的第一类和第三类手段的结合——一遍扫描时多记一点，同时利用有序这条结构性质。归并排序本身就是把数组不断二分、分别排序、再合并的过程；在「合并」这一步顺手做一件事：每次从右半区取出一个元素（意味着它比左半区当前剩余的所有元素都小），就把「左半区剩余元素的个数」累加进逆序对总数——这一步不需要额外遍历，合并本来就要走这一趟。

long long mergeCount(int a[], int temp[], int left, int mid, int right) {
    int i = left, j = mid + 1, k = left;
    long long inv = 0;
    while (i <= mid && j <= right) {
        if (a[i] <= a[j]) {
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
            inv += (mid - i + 1);    // a[i..mid] 全都比 a[j] 大，一次性累加
        }
    }
    while (i <= mid)   temp[k++] = a[i++];
    while (j <= right) temp[k++] = a[j++];
    for (int t = left; t <= right; t++) a[t] = temp[t];
    return inv;
}

long long mergeSortCount(int a[], int temp[], int left, int right) {
    if (left >= right) return 0;
    int mid = left + (right - left) / 2;
    long long inv = mergeSortCount(a, temp, left, mid);
    inv += mergeSortCount(a, temp, mid + 1, right);
    inv += mergeCount(a, temp, left, mid, right);
    return inv;
}

long long countInversionsOptimal(int a[], int n) {
    int *temp = (int *)malloc(n * sizeof(int));
    long long inv = mergeSortCount(a, temp, 0, n - 1);
    free(temp);
    return inv;
}

从暴力解升级过来，几处最容易翻车：

累加的时机和累加的值。 只有当 a[j] < a[i]（右半区元素更小、被优先取出）时才累加，累加的值是 mid - i + 1——这是左半区当前还没被取走的元素个数，不是整个左半区的长度。i 会随着合并推进而增大，这个值也要跟着变。
累加发生在归并排序本来就要做的合并步骤里，不需要额外增加一次遍历。 这道题的「最优性」恰恰在于没有为了统计逆序对单独加一趟扫描，而是让排序过程顺带算出答案——如果写成「先排序、再单独扫一遍统计」，复杂度虽然还是 $O (n \log n)$ 级别但白白多做了一次线性扫描，不是最紧凑的写法。
计数用 long long，不能用 int。 逆序对数量最坏情况下（完全逆序的数组）是 $(\binom{n}{2})$ 量级，n 稍微大一点就会超过 int 的范围，考场上这类「数值可能超范围」的细节和算法思路本身同样重要。
左右两个半区各自递归排序统计完之后，还要加上合并阶段产生的逆序对——三部分逆序对互不重复、缺一不可。 左半区内部的逆序对由左边的递归调用负责，右半区内部的由右边的递归调用负责，跨越左右两个半区的逆序对只能在合并这一步统计，漏掉任何一部分结果都不完整。

复杂度：归并排序本身是 $O (n \log n)$ ，累加逆序对只是在合并过程中多做一次常数时间的加法，不改变量级，整体仍是 $O (n \log n)$ ；辅助数组占 $O (n)$ 空间，递归栈 $O (\log n)$ 。相比暴力解的 $O (n^{2})$ ，是数量级的提升。

两版对照跑一遍

同一组输入 a = [2,4,1,3,5]（答案：3 个逆序对）。先看双重循环——逐对枚举比较：

加载可视化中...

再看归并排序顺带统计——合并两个有序半区时一次性累加一批逆序对：

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应。

等价方法与升级空间

也可以用树状数组（BIT）统计逆序对：从右往左扫描数组，每处理一个元素就查询「当前已插入的、比它小的元素个数」，然后把它插入树状数组，复杂度同样是 $O (n \log n)$ 。这个做法不在 408 数据结构的核心大纲内（树状数组通常不作为考纲要求的数据结构），但思路上和归并排序统计法是等价的替代方案。
为什么不必进一步优化：逆序对统计本质上和排序是同一个问题——排好序这件事本身就需要 $Ω (n \log n)$ 次比较（基于比较的排序下界），而逆序对数量恰好能在排序过程中顺带算出来， $O (n \log n)$ 已经是这道题的最优复杂度。

下一步

看归并排序的分治合并演示：归并排序可视化
回到方法论源头：「暴力解到最优解」真题专题总纲

求逆序对数：从双重循环到归并顺带统计 ​

题目 ​

第一步：把暴力解写对——双重循环枚举 ​

它值多少分 ​

暴力解的浪费在哪 ​

智慧化改造：归并排序顺带统计 ​

两版对照跑一遍 ​

等价方法与升级空间 ​

下一步 ​