我试图计算在一个100，000整数数组的合并排序过程中发生的反转数。数组中的值没有特定的顺序。我的问题很简单，在合并排序算法中，我应该在哪里应用反转计数器？下面如果合并排序算法本身，之后的图像是我建议放置反转计数器的地方。文件读取正确，合并排序正确，我只是问我的位置是否倒置计数器是准确的。任何意见将不胜感激！
我已编辑页面，仅包含合并功能
void merge(vector<int> &left, vector<int> &right, vector<int> &array, int &inversionCount)
{
int leftSize = left.size();
int rightSize = right.size();
int i = 0, l = 0, r = 0;
while (l < leftSize && r < rightSize)
{
if (left[l] < right[r])
{
int temp1 = l;
while ((right[r] > left[temp1]) && temp1 < left.size() - 1)
{
inversionCount++;
temp1++;
}
array[i] = left[l];
i++;
l++;
}
else if (right[r] < left[l])
{
int temp1 = r;
while ((left[l] > right[temp1]) && temp1 < right.size() - 1)
{
inversionCount++;
temp1++;
}
array[i] = right[r];
i++;
r++;
}
else
{
array[i] = right[r];
i++;
r++;
}
}
while (l < leftSize)
{
array[i] = left[l];
i++;
l++;
}
while (r < rightSize)
{
array[i] = right[r];
i++;
r++;
}
}字符串
1条答案
按热度按时间eqqqjvef1#
从你的评论中，听起来你走在正确的道路上。
然而，让我们看看一些随机数的情况，跳过前几次合并。我们将考虑左[4，5，7，8，9]和右[1，2，3，5，6]的情况。也许已经计算了一些反演，但我们将从这里开始。
首先，我们检查left[4]是否大于right[1]。是的，所以我们必须增加反转计数器。然而，在这种情况下，[4]也大于[2]和[3]，这也必须考虑。
问题是，我们如何才能做到这一点？当我们意识到than [4]大于[1]时，我们可以在右数组中开始另一个循环，递增我们的反转计数器，直到我们遇到一个大于或等于4的值，然后我们停止。所以在这种情况下，我们对[1]，[2]和[3]执行[4]+1，然后我们在右[5]处停下来。这给我们留下了+3，然后我们在新数组中放入4，然后从左[5]开始，再次向上计数。
显然，我们必须在开始检查之前保存right[1]的索引，否则MergeSort算法可能会出错。
这是一种幼稚的方法，因为当我们看到left[5]时，真的没有理由一路向上计数，因为我们知道left[5] > left[4]，并且我们已经知道left[4]大于right[]数组中的几个值。对于100，000个值，这种幼稚可能会导致程序慢很多。