我已经基于CLRS Merge Sort伪代码实现了一个计算倒置的合并排序,但是答案不正确,不对数组进行排序,也没有正确计算倒置。
求反的定义:设A [1..n]为n个不同整数的数组。如果i
我使用了按引用传递来处理相同的 vector 。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}。
最佳答案
好了,已经过去了几个月了,尽管我确实做了代码实现返回排序数组的工作,但在反转计数上仍然存在错误。今天我致力于它并解决它,所以就在这里。
首先,在mergeInvCount方法的最后一个for中,使用基于1的索引访问arr,因此它不起作用,修复了将其减去1以使用基于0的索引进行访问的问题。
其次,在比较两个辅助数组以进行合并的条件下,必须计数一个倒数的情况是不正确的。
当左辅助数组上的元素大于右辅助数组上的元素时,对于该数字,我们必须计算1个倒数,其后的每个其他元素除1个“无限”共代蛋白外,都必须计算1个倒数。由于辅助数组是由于递归调用而排序的,因此是正确的。
它在左辅助数组从索引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;
}
关于c++ - 基于CLRS的合并排序C++上的算法简介(带反转计数),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56963509/