时间戳

首页 > 解决方案 > 基于 CLRS 的合并排序 C++ 上的算法介绍，带倒数计数

c++ - 基于 CLRS 的合并排序 C++ 上的算法介绍，带倒数计数

问题描述

我已经实现了一个基于 CLRS 合并排序伪代码计算反转的合并排序，但答案不正确，不对数组进行排序，也没有正确计算反转。

求逆的定义：令 A[1..n] 是一个由 n 个不同整数组成的数组。如果 i < j 且 A[i] > A[j]，则 (i,j) 对称为 A 的反转。

我使用通过引用传递来处理相同的向量。

int mergeSortInvCount(vector<int> &arr, int izq, int der);
int mergeInvCount(vector<int> &arr, int izq, int mitad, int der);

void invCountRecursivo(vector<int> &arr, int n){



    int numInversiones = mergeSortInvCount(arr, 1, n);
    cout << "Num inversiones:" << numInversiones << endl;
    for(int i=0; i < n; i++){

        cout<<arr[i]<<endl;
    }
}

int mergeSortInvCount(vector<int> &arr, int izq, int der){

    int invCount = 0;

    if(izq < der){

        int mitad = (izq + der)/2;

        invCount = mergeSortInvCount(arr, izq, mitad);
        invCount += mergeSortInvCount(arr, mitad+1, der);
        invCount += mergeInvCount(arr, izq, mitad, der);
    }

    return invCount;
}

int infinito = numeric_limits<int>::max();

int mergeInvCount(vector<int> &arr, int izq, int mitad, int der){

    int n1 = mitad - izq + 1;
    int n2 = der - mitad;

    int invCount = 0;

    vector<int> vectorIzq;
    vector<int> vectorDer;

    for(int k=0;k<n1;k++){

        vectorIzq.push_back(arr[izq+k-1]);
    }

    vectorIzq.push_back(infinito);

    for(int k=0;k<n2;k++){

        vectorDer.push_back(arr[mitad+k]);
    }

    vectorDer.push_back(infinito);

    int i = 0;
    int j = 0;

    for(int k = izq; k <= der; k++){

        if(vectorIzq[i] <= vectorDer[j]){

            arr[k] = vectorIzq[i];
            i++;
        }
        else{

            arr[k] = vectorDer[j];
            j++;
            invCount += (mitad - i);
        }
    }

    return invCount;
}

对于输入：{4,3,1,8,2} 和 5，正确答案是 6 次反转，排序后的数组是 {1,2,3,4,8}。它返回 5 个反转和 {4,4,4,3,4}。

标签： c++arraysmergesortclrsinversion

解决方案

好吧，几个月过去了，尽管我确实完成了返回排序数组的代码实现，但反转计数仍然存在错误。今天我研究它并解决了它，所以就在这里。

首先，在 mergeInvCount 方法的最后一个 for 中，arr 使用从 1 开始的索引访问，所以它不起作用，修复了它减去 1 以使用从 0 开始的索引访问。

其次，在比较两个辅助数组进行合并的条件下，我们必须计算反转的情况是不正确的。

当左侧辅助数组中的元素大于右侧辅助数组中的元素时，我们必须为该数字计数 1 次反转，并为其后面的每个其他元素计数 1，除了“无限”comodin。由于辅助数组是由于递归调用而排序的，因此是正确的。

它在左辅助数组从索引 1 开始时起作用，因为减法 (mid - i) 返回有序辅助数组中剩余的元素数，而不考虑 comodin。

但是当我们合并数组并且左边不是从 1 开始时，减法无法返回数组中实际索引之后的正确元素数。

所以解决这个问题的方法是使用n1，它存储了左侧辅助数组中的元素个数。这样， (n1 - i) 返回正确的数字。

这是工作代码：

int mergeSortInvCount(vector<int> &arr, int izq, int der);
int mergeInvCount(vector<int> &arr, int izq, int mitad, int der);

void invCountRecursivo(vector<int> &arr, int n){

    int numInversiones = mergeSortInvCount(arr, 1, n);
    cout << "Num inversiones:" << numInversiones << endl;
    cout << "Ordered array, ascendant order" << endl;
    for(int i=0; i < n; i++){
        cout<<arr[i]<<endl;
    }
}

int mergeSortInvCount(vector<int> &arr, int izq, int der){

    int invCount = 0;

    if(izq < der){

        int mitad = (izq + der)/2;
        invCount = mergeSortInvCount(arr, izq, mitad);
        invCount += mergeSortInvCount(arr, mitad+1, der);
        invCount += mergeInvCount(arr, izq, mitad, der);
    }

    return invCount;
}

int infinito = numeric_limits<int>::max();

int mergeInvCount(vector<int> &arr, int izq, int mitad, int der){

    int n1 = mitad - izq + 1;
    int n2 = der - mitad;

    int invCount = 0;

    vector<int> vectorIzq;
    vector<int> vectorDer;

    for(int k=0;k<n1;k++){

        vectorIzq.push_back(arr[izq+k-1]);
    }

    vectorIzq.push_back(infinito);

    for(int k=0;k<n2;k++){

        vectorDer.push_back(arr[mitad+k]);
    }

    vectorDer.push_back(infinito);

    int i = 0;
    int j = 0;

    for(int k = izq; k <= der; k++){

        if(vectorIzq[i] <= vectorDer[j]){

            arr[k-1] = vectorIzq[i];
            i++;
        }
        else{

            arr[k-1] = vectorDer[j];
            j++;
            invCount += (n1 - i);
        }
    }

    return invCount;
}

int main(){

    vector<int> v = {4,3,1,8,2};
    invCountRecursivo(v, 5);
    // Returns 6, the correct # of inversions of A

    return 0;
}

推荐阅读