利用mergesort c++在向量中计数倒置

Question

对于我发送给它的一些输入，该算法将返回一个off错误。我首先用数组编写了merge_sort和inversion_count，这给出了正确的反转次数。一旦我转换成向量，我就会得到1作为输入: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 ------^

显然，您打算为调用方修改这个向量，因为在例程结束时：

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需要使用引用。

注意:一旦您学习了迭代器，您将很高兴地使用它们来建模类似的事情。它不仅使代码更简洁，而且自动允许在任何支持适当迭代器类型的序列容器上使用它。