C++ 中的 Mergesort 实现错误

Question

我正在学习实现用于计算倒置的归并排序算法。这是我当前的合并排序实现。但是它不起作用，因为它不是 return 排序数组。谁能告诉我在我编写的这段代码中做错了什么？它应该对输入到函数中的数组 v 进行排序。

void mergeCountInversion(vector<int> v, int l, int r)
{
    if (l >= r)
    {
        return;
    }

    int m = (l + r)/2;  

    //call merge sort to return two sorted arrays
    mergeCountInversion(v, l, m);
    mergeCountInversion(v, m+1, r);

    int left = l;
    int right = m+1;
    std::vector<int> vtemp ;

    //merge and sort the two sorted array, storing the sorted array in vtemp
    for (int k = l; k <= r; ++k){
        if (left >= m+1)
        {
            vtemp.push_back(v[right]);
            right++;
        }
        else if (right > r)
        {
            vtemp.push_back(v[left]);
            left++;
        }
        else
        {
            if (v[left] <= v[right])
            {
                vtemp.push_back(v[left]);
                left++;
            }
            else{
                vtemp.push_back(v[right]);
                right++;
                count += m + 1 - left;
            }
        }
    }

    //replace v with the sorted array vtemp
    for (int i = 0; i < vtemp.size(); ++i)
    {
        v[l+i] = vtemp[i];
    }
}

Answer 1

你定义了

void mergeCountInversion(vector<int> v, int l, int r)

那么你先递归调用mergeCountInversion，调用返回后修改v。

问题是在递归调用中对 v 所做的更改将永远不会被看到，因为 v 是 通过值 传递的。

尝试通过v 参考:

void mergeCountInversion(vector<int>& v, int l, int r)

这样所有调用都在 v.

的同一个副本上工作

Answer 2

您的代码中存在几个问题。

您正在按值传递矢量，但您应该按引用传递它。

如果将函数声明为 void 则不能 return 0;，只需 return;.

当您创建 vtemp 时，您应该确切地知道它的大小：r - l。所以你可以为它预留内存，你不需要push_back.

您也必须将计数传递给该函数。

你的函数可以是：

void mergeCountInversion(vector<int> & v, int l, int r, int & count) {
    if (l >= r) return;

    int m = (l + r)/2;  

    //call merge sort to return two sorted arrays
    mergeCountInversion(v, l, m, count);
    mergeCountInversion(v, m+1, r, count);

    int left = l;
    int right = m+1;
    std::vector<int> vtemp(r-l);

    //merge and sort the two sorted array, storing the sorted array in vtemp
    for (int k = l; k <= r; ++k) {
        if (left >= m+1) {
            vtemp[k] = v[right];
            right++;
        }
        else if (right > r) {
            vtemp[k] =  v[left];
            left++;
        }
        else {
            if (v[left] <= v[right]) {
                vtemp[k] = v[left];
                left++;
            }
            else {
                vtemp[k] = v[right];
                right++;
                count += m + 1 - left;
            }
       }
    }

    //replace v with the sorted array vtemp
    for (int i = 0; i < vtemp.size(); ++i)
    v[l+i] = vtemp[i];
}

C++ 中的 Mergesort 实现错误

Error with Mergesort implementation in C++

c++

algorithm

mergesort