在此合并排序算法中，我应该将反转计数器放在哪里？-解网

问：

我正在尝试计算在 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++;
    }

}

C++ mergesort 反转

@PaulMcKenzie 就我而言，在纸面上，每当右手数字小于左手数字时，就会发生倒置。因此，这使我假设反转计数器应该仅在合并函数中的 right[r] < left[l] 时递增，这给我留下了 776,644 个反转。对于这么多价值观来说，这听起来并不遥远，但我仍然觉得我好像忘记了什么

0赞 PaulMcKenzie 11/10/2023

尝试较小的样品集的意义在于，它使调试更容易。如果使用小样本的手动计算（假设它是正确的）与程序生成的内容不匹配，那么就从它开始。如果 100,000 个项目不起作用，尝试 10 个项目是没有意义的。

2赞 PaulMcKenzie 11/10/2023

if (left[l] < right[r])——这难道不是“反转”发生的地方吗？如果你的意思是“反转”是“交换物品”，那么这将是明显的地方（而且部分也将是第二个地方）。else

答：

1赞 Harrison Carter 11/10/2023 #1

从您的评论来看，听起来您走在正确的轨道上。

但是，让我们看一些随机数的情况，并跳过前几个合并。我们将以 left[4,5,7,8,9] 和 right[1,2,3,5,6] 为例。也许已经计算了一些反转，但我们将从这里开始。

首先，我们检查 left[4] 是否大于 right[1]。是的，所以我们必须增加我们的反转计数器。但是，在这种情况下，[4] 也大于 [2] 和 [3]，这也必须考虑在内。

问题是，我们怎样才能做到这一点？好吧，当我们意识到 than [4] 大于 [1] 时，我们可以在正确的数组内开始另一个循环，递增我们的反转计数器，直到我们遇到一个大于或等于 4 的值，然后我们停止。因此，在这种情况下，我们将 [4] 与 [1]、[2] 和 [3] 对立 +1，然后停在右边 [5]。这给我们留下了 +3，然后我们在新数组中放下 4，然后从 left[5] 重新开始，再次计数。

显然，在开始此检查之前，我们必须保存 right[1] 的索引，否则 MergeSort 算法可能会搞砸。

不过，这是一种幼稚的方法，因为当我们查看 left[5] 时，真的没有理由一直往上数，因为我们知道 left[5] > left[4]，并且我们已经知道 left[4] 大于 right[] 数组中的几个值。对于大约 100,000 个值，这种幼稚可能会导致您的程序速度变慢很多。

在此合并排序算法中，我应该将反转计数器放在哪里？

Where do I put the inversion counter in this merge sort algorithm?

评论

评论