基于分治的递归Count Inversions逆序对统计算法错误排查

你的代码核心问题是忽略了逆序对统计算法是基于归并排序实现的，统计跨左右逆序对的前提是左右两个子数组已经各自有序，但你当前的实现完全没有排序相关的步骤：

1. 函数参数是const引用，无法修改传入的数组，递归计算完子数组的逆序对后，无法将排序后的子数组返回给上层使用
2. 统计完跨左右的逆序对后，缺失了合并两个有序子数组、赋值回当前数组的步骤，上层递归拿到的子数组始终是乱序的，双指针计数的逻辑自然不成立

我们用你的测试用例{2,1,3,1,2}验证：原代码统计完左右子数组的逆序对后，左子数组仍是{2,1}、右子数组仍是{3,1,2}，都是乱序状态，跨逆序对统计时会漏掉2（索引0）>1（索引3）这1个逆序对，最终结果就是3而不是正确的4。

unsigned int countInversions (std::vector<int> & A){
    if (A.size() <= 1){
        return 0;
    }
    std::size_t const middle = A.size()/2;
    unsigned int inversions = 0;

    std::vector<int> A_l(A.begin(), A.begin() + middle);
    inversions += countInversions(A_l);

    std::vector<int> A_r(A.begin() + middle, A.end());
    inversions += countInversions(A_r);

    // 统计跨左右的逆序对（此时A_l、A_r已经各自有序）
    unsigned int i=0, j=0;
    while (i < A_l.size() && j < A_r.size()){
        if (A_l[i] > A_r[j]){
            inversions += A_l.size() - i;
            j++;
        }
        else{
            i++;
        }
    }

    // 新增：合并两个有序数组，赋值回A，供上层使用
    i = 0; j = 0;
    unsigned int k = 0;
    while (i < A_l.size() && j < A_r.size()) {
        if (A_l[i] <= A_r[j]) {
            A[k++] = A_l[i++];
        } else {
            A[k++] = A_r[j++];
        }
    }
    while (i < A_l.size()) A[k++] = A_l[i++];
    while (j < A_r.size()) A[k++] = A_r[j++];

    return inversions;
}

这里把原来的middle - i改成了A_l.size() - i，逻辑上更严谨，避免后续修改middle定义时出错。如果调用时不想修改原数组，传入原数组的副本即可。

内容的提问来源于stack exchange，提问作者NiRvanA