实现归并排序代码时不能计算所有的倒置

Question

我一直在试图弄清楚如何让这段代码计算所有的倒置，但我似乎无法理解。根据我的理解，这段代码应该计算所有的反转，但它在许多测试用例中失败，在正确的方向上轻推，甚至整个修复都会受到赞赏。

代码：

int countInversion(vector<int>& v, int& inv) {
    if(v.size() > 1) {
        vector<int> left(v.begin(), v.begin() + v.size()/2);
        vector<int> right(v.begin() + v.size()/2, v.end());

        countInversion(left, inv);
        countInversion(right, inv);

        int l = 0; int r = 0;

        for(int i = 0; i < v.size(); i++) {
            if(r >= right.size() || (l < left.size() && left[l] < right[r])) {
                v[i] = left[l++];
            } else {
                if(right[r] < left[l]) inv += left.size() - l;
                v[i] = right[r++];  
            } 
        }
    } return inv;
}

有效的代码（我在互联网上找到的）非常低可读性有人可以帮助我理解它吗？更重要的是，指出我的代码究竟遗漏了什么，是否可以纠正我的代码以正确计数？谢谢！

代码 2:

long long ans = 0;

void mergei(int a[],int i,int j) {
    int ni = ((i+j)/2) + 1, nj = j + 1;
    int s = i;
    int* arr = new int [j - i + 1];
    j = ni;
    int k = 0;

    while(i < ni && j < nj) {
        if(a[i] <= a[j]) {
            arr[k] = a[i++];
        } else {
            arr[k] = a[j++];
            ans += (ni - i);
        } k++;
    }

    for(; i < ni; i++, k++) arr[k] = a[i];
    for(; j < nj; j++, k++) arr[k] = a[j];
    for(k = 0; s < nj; s++, k++) a[s] = arr[k];
    delete [] arr;
}

void m_sort(int a[],int i,int j) {
    if(i < j) {
        m_sort(a, i, (i+j)/2);
        m_sort(a, ((i+j)/2) + 1, j);
        mergei(a, i, j);
    }
}

Answer 1

我终于找到了一种使用我的代码来解决它的方法，我确信对 if else 块进行一些更改或者我添加反转的方式会修复它，它只是必须，这就是重点mergesort，这就是为什么我坚持以这种方式解决它，而不是仅仅使用其他代码。问题是；我正在做 left[l] < right[r] ，如果它是左或右，这对合并无关紧要，但对于反转，只需要将其更改为 left[l] <= right[r].

long countInversions(vector<int>& arr, long& inv) {
    if(arr.size() > 1) {
        vector<int> left(arr.begin(), arr.begin() + arr.size()/2);
        vector<int> right(arr.begin() + arr.size()/2, arr.end());

        countInversions(left, inv);
        countInversions(right, inv);

        int l = 0; int r = 0;

        for(int i = 0; i < arr.size(); i++) {
            if(r >= right.size() || (l < left.size() && left[l] <= right[r])) {
                arr[i] = left[l++];
                // inv += r;
            } else {
                arr[i] = right[r++];
                inv += left.size() - l;
            }
        }
    } return inv;
}

稍微好一点且更易读的代码是：

long countInversions(vector<int>& v) {
    if(v.size() <= 1) return 0;

    vector<int> left(v.begin(), v.begin() + v.size()/2);
    vector<int> right(v.begin() + v.size()/2, v.end());

    long inv = countInversions(left) + countInversions(right);

    int l = 0, r = 0;

    for(int i = 0; i < v.size(); i++) {
        if(r >= right.size() || (l < left.size() && left[l] <= right[r])) {
            v[i] = left[l++];
            // inv += r;
        } else {
            v[i] = right[r++];
            inv += left.size() - l;
        }
    }     
    return inv;
}

实现归并排序代码时不能计算所有的倒置

Can't count all the inversions while implementing mergesort code

c++

sorting

algorithm

mergesort