C++如何使用归并排序统计逆序对-C++-PHP中文网

归并排序过程中可在merge阶段顺手统计逆序对：当arr[i] > arr[j]时，累加mid - i + 1到引用传递的long long计数器，因右段元素arr[j]小于左段剩余所有元素；需注意下标边界、相等不计、临时数组拷贝起始位置为l。

c++如何使用归并排序统计逆序对

归并排序过程中怎么顺手统计逆序对

归并排序天然适合统计逆序对，因为每次 merge 时，右半段某个元素 arr[j] 被提前放入临时数组，说明它比左半段从当前指针 i 到末尾的所有元素都小——这些就是和它构成逆序对的元素。数量就是 mid - i + 1（假设左半段区间是 [l, mid]）。

关键不是“额外写一个函数”，而是把计数逻辑嵌进标准归并过程里，不破坏原有结构。

递归分治后，在 merge 阶段，当 arr[i] > arr[j]（即右段元素更小），累加 mid - i + 1 到全局或引用传入的计数器
必须用 long long 存逆序对总数，int 很容易溢出（比如 1e5 个元素完全逆序时有约 5e9 对）
不要在 merge 前清空临时数组，直接覆盖写入即可；临时空间建议用局部 vector 或预分配数组，避免频繁 new/delete

为什么不能只靠 `sort` + 索引映射来算

有人想先用 std::sort 得到排序后下标，再用树状数组或线段树反推逆序对——这可行但绕远、易错，且多引入 O(n log n) 空间和常数开销。而归并法是原地（除临时数组外）、一次遍历、逻辑清晰的解法。

std::sort 是黑盒，无法在排序过程中插手计数；你无法知道它内部哪两个元素发生了交换
索引映射法需要额外维护位置关系，处理重复元素时边界容易写错（比如相等时是否算逆序？按定义：不等且前面大于后面才算，所以 arr[i] > arr[j] 才计，== 不计）
归并法天然稳定，重复元素不会误增计数；而快排类方法若没写好 partition，可能漏掉跨块的逆序对

`merge` 函数里哪些细节最容易导致计数错误

最常见的是下标越界和区间划分不一致。比如递归调用时写成 merge_sort(arr, l, mid) 和 merge_sort(arr, mid+1, r)，那 merge 里左半段长度就是 mid - l + 1，右半段是 r - mid，此时计算逆序对要写成 (mid - i + 1)，其中 i 是左段当前下标，mid 是左段右边界。

C++

"空空如也"

下载

别把 mid 当作长度用，它是下标；错误写法：cnt += (j - mid) 或 cnt += (len_left - i)（没考虑 l 偏移）
合并循环中，只有进入 arr[i] > arr[j] 分支时才计数；如果写成 arr[i] >= arr[j]，会把相等元素也计入，导致结果偏大
临时数组拷贝回原数组时，起始位置必须是 l，不是 0；否则只改了局部，上层看到的还是乱序

完整可跑的最小示例长什么样

下面这段代码去掉注释就能编译运行，核心就三处修改：参数加 long long& cnt、merge 中加计数、递归调用传同一引用：

void merge(vector<int>& arr, int l, int mid, int r, long long& cnt) {
    vector<int> tmp(r - l + 1);
    int i = l, j = mid + 1, k = 0;
    while (i void merge_sort(vector<int>& arr, int l, int r, long long& cnt) {
if (l >= r) return;
int mid = l + (r - l) / 2;
merge_sort(arr, l, mid, cnt);
merge_sort(arr, mid + 1, r, cnt);
merge(arr, l, mid, r, cnt);
}</int></int></int>

调用时：先初始化 long long cnt = 0，再 merge_sort(arr, 0, n-1, cnt)。注意 arr 是传引用，否则白改。

真正容易被忽略的是：计数变量必须是引用传递，且全程不重置；如果在每层递归里定义局部 cnt 再返回，合并时容易漏掉子问题的贡献，或者因作用域混乱导致值丢失。