原始题目

下面归并排序代码横线处应该填什么？

int mergeSort(int a[], int temp[], int left, int right) {
    if (left >= right) return 0;
    int mid = left + (right - left) / 2;
    int count = mergeSort(a, temp, left, mid) + mergeSort(a, temp, mid + 1, right);
    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right) {
        if (a[i] <= a[j]) temp[k++] = a[i++];
        else {
            temp[k++] = a[j++];
            ___;
        }
    }
    while (i <= mid) temp[k++] = a[i++];
    while (j <= right) temp[k++] = a[j++];
    for (int i = left; i <= right; i++) a[i] = temp[i];
    return count;
}
  • A. count++
  • B. count += mid - i + 1
  • C. count += j - left
  • D. count += right - j + 1

答案：B（count += mid - i + 1）

完整写法：

int mergeSort(int a[], int temp[], int left, int right) {
    if (left >= right) return 0;
    int mid = left + (right - left) / 2;
    int count = mergeSort(a, temp, left, mid) + mergeSort(a, temp, mid + 1, right);
    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right) {
        if (a[i] <= a[j]) temp[k++] = a[i++];
        else {
            temp[k++] = a[j++];
            count += mid - i + 1;   // 逆序对累计
        }
    }
    while (i <= mid) temp[k++] = a[i++];
    while (j <= right) temp[k++] = a[j++];
    for (int i = left; i <= right; i++) a[i] = temp[i];
    return count;
}

图解：合并阶段如何数逆序对

归并排序：合并时如何数逆序对 左子数组已排序 [3, 5, 7]，右子数组已排序 [2, 4, 8]，比较 a[i] 与 a[j] 左 [left, mid] 3 5 7 i=0 右 [mid+1, right] 2 4 8 j=0 比较：a[i]=3 > a[j]=2 → 走 else 分支 左边从 i 到 mid 的所有元素都 > a[j]，即 3、5、7 都与 2 构成逆序对 3 个元素都 > 2 count += mid - i + 1; mid - i + 1 = 2 - 0 + 1 = 3 → 累计新增 3 个逆序对 关键点：统计的是“左边剩余全部”，不是只数 a[i] 与 a[j] 这一个。若写 count++ 会严重少算。 复杂度：每次合并 O(n)，共 log n 层 → 总 O(n log n)，适合 n 达 10^5 的规模。

原理

左边子数组 [left, mid]、右边 [mid+1, right] 都已经在各自区间有序。当 a[i] > a[j]（走 else）时：

  • 因为左边有序，a[i] 是左边未处理部分里最小的
  • 它都比 a[j] 大，那 a[i] 后面的 a[i+1], … , a[mid] 自然也都比 a[j] 大
  • 所以 a[j] 和左边剩余所有元素都构成逆序对，数量是 mid - i + 1

这就是为什么不能写 count++——它只数了「这一对」，漏掉了左边整批。

逐项排除

选项 判断 错在哪
A. count++ ❌ 只数了 (i, j) 这一对，漏掉左边 i+1…mid 那一批，结果严重偏小
B. count += mid - i + 1 ✅ 左边剩余全部元素都与 a[j] 构成逆序对
C. count += j - left ❌ 用右边下标算逆序对数，量纲完全不对
D. count += right - j + 1 ❌ 这是右边剩余元素个数，与当前比较无关

复杂度

操作 时间 空间
暴力枚举所有对 \(O(n^2)\) \(O(1)\)
归并排序法（本题） \(O(n \log n)\) \(O(n)\)

\(n\) 较大（如 \(10^5\)）时，暴力会超时，必须用归并或树状数组/线段树。

易错点

  1. <= 的位置：a[i] <= a[j] 时归并，等于不算逆序对，mid - i + 1 仍正确。
  2. 重复元素：用 <= 把等于归入“不逆序”，避免重复计数（某些题要求逆序对严格 > 才算）。
  3. int 溢出：逆序对总数最大约 \(n(n-1)/2\)，n = 10^5 时约为 \(5 \times 10^9\)，必须开 long long，否则中间结果溢出。
  4. 稳定计数：归并排序本身稳定，逆序对计数结果与具体相等元素顺序无关（前提是严格 > 才算）。

考点总结（CSP-J/S 初赛、程序填空）

  1. 出现“逆序对”+“归并排序”组合 → else 分支填 count += mid - i + 1。
  2. 记忆口诀：左边还有几个没处理，就新增几个逆序对。
  3. 总逆序对 = 左半内部 + 右半内部 + 合并时跨左右的。count 在递归里一路累加返回。
  4. n 大时记得 long long，否则爆 int。

来源

本文解析参考自：https://123.hnai.net/nuclq

思考题

如果要求“逆序对”改为“顺序对”（即 a[i] < a[j]，i < j 的对数），应该怎么改这行代码？

答案 顺序对等于“总对数 − 逆序对 − 相等对数”。更直接的改法：把条件改成 a[i] < a[j] 时统计，else 里对应 a[j] <= a[i] 的情况累计。常用写法是用总对数 \(n(n-1)/2\) 减去逆序对与相等对的数量，避免改核心逻辑。