c++ - 使用mergesort c++计算 vector 中的反转

Question

对于我发送给它的一些输入，该算法返回一个错误。我先用数组写了merge_sort和inversion_count；这返回了正确数量的反转。一旦我过渡到 vector ，我就会收到以下输入的一个: 2 4 1 3 5

一双新鲜的眼睛将不胜感激。

vector<int> a;
object o;

length = a.size();
inv = o.count_inversion(a, 0, length-1);



int inversion::merge_and_count(vector<int> vector1, int alpha, int omega)
{
    int inversion = 0;
    int mid = (alpha + omega) / 2;
    int i = alpha;
    int j = mid + 1;
    int lastITR = 0;
    vector<int> final(omega - alpha + 1);


while (i <= mid && j <= omega) {
    if (vector1[i] <= vector1[j])
    {
            final[lastITR++] = vector1[i++];
    }
    else
    {
            final[lastITR++] = vector1[j++];
            inversion += mid - i + 1;
    }
}

while (i <= mid)
    {
    {
    final[lastITR++] = vector1[i++];
    }

    while (j <= omega)
    {
    final[lastITR++] = vector1[j++];
    }

    for (int k=0 ; k < omega-alpha+1; k++)
    {
    vector1[k+alpha] = final[k];
    }

return inversion;
}


int inversion::count_inversion(vector<int> vector1, int a, int b)
{
int x, y, z, mid;

if (a >= b)
    {
            return 0;
    }

mid = (a+b)/2;

x = count_inversion(vector1, a, mid);
y = count_inversion(vector1, mid+1, b);
z = merge_and_count(vector1, a, b);

return x + y + z;
}

Answer 1

可能导致您的问题的一件事如下(注意:我不知道您要做什么，但我认为这真的不重要):

int inversion::merge_and_count(vector<int> vector1, int alpha, int omega)
// note: pass by *value*, not reference ------^

很明显，您打算为调用者实际修改此 vector ，因为在您的例程结束时:

for (int k=0 ; k < omega-alpha+1; k++)
{
    vector1[k+alpha] = final[k];
}

本质上，您正在构建一个合并的 final ，然后将其复制到即将被销毁的 vector 中。来电端vector<int>完成后保持不变，保持与之前相同。

使用引用修复此问题:

int inversion::merge_and_count(vector<int>& vector1, int alpha, int omega)
// note: reference -----------------------^

有一些潜在的问题，但这很可能是让您感到悲伤的问题。按值传递给 count_inversion应该没问题，因为不清楚你想在那里修改调用者 vector ，如果这只是计算倒置，你可能不想这样做。但是merge_and_count需要使用引用。

注意:一旦您学习了迭代器，您就会愉快地使用它们来建模这样的东西。它不仅使代码更简洁，而且自动允许它在支持适当迭代器类型的任何序列容器上使用。