1

对于我发送给它的一些输入，该算法会返回一个错误。我先用数组写了merge_sort和inversion_count；这给出了正确数量的反转。一旦我转换到向量，我就会收到以下输入：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;
}
4

1 回答 1

2

可能导致您的问题的一件事如下（注意：我不知道您要做什么，但我认为这并不重要）：

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

显然，您打算为调用者实际修改此向量，因为在您的例程结束时：

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

本质上，您正在构建一个合并的final，然后将其复制到即将被销毁的向量中。完成此操作后，调用方vector<int>保持不变，保持与之前相同。

通过使用参考解决此问题：

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

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

注意：一旦你学会了迭代器，你就会很乐意用它们来建模这样的东西。它不仅使代码更简洁，而且自动允许在任何支持正确迭代器类型的序列容器上使用它。

于 2013-10-11T05:27:34.550 回答