0

我正在尝试编写代码来查找数字数组中的反转。我已经看到使用合并排序正确执行此操作的算法，但对逻辑有疑问。

为什么我们必须计算左右子数组中的反转以及两者之间的反转？我的意思很明显这是正确的，但为什么我们不能只计算合并步骤中的所有反转呢？事实证明，在进行合并的每一级都可以直接计算反转的次数，并且在生成两倍大小的子数组后，它的任何两个元素的相对顺序在后续合并步骤中永远不会改变，这意味着我们永远不会计算任何最终不会是反转的反转。那么，逻辑有什么问题，因为它没有给出正确的答案。

如果你愿意，我可以用例子和/或代码解释更多；故意没有包含代码，所以没有人怀疑这是家庭作业。

编辑：到目前为止，我没有发现逻辑有任何问题，而是代码中的一个错误导致了错误的答案。

因此，这是在数组中查找反转的方法：

private void findInversions(int begin, int end, int count) {
    if (end - begin < 1)
        return;
    int middle = (begin + end) / 2;
    findInversions(begin, middle, count);
    System.out.println("But here count is " + count + " and I can't find why.");
    findInversions(middle + 1, end, count);
    count = mergeAndCount(begin, middle, end, count);
    System.out.println("count now is: " + count);
}

该mergeAndCount()方法的工作方式显而易见：

private int mergeAndCount(int begin, int middle, int end, int count) {

    int[] result = new int[end - begin + 1];
    int aptr = begin;
    int bptr = middle + 1;
    for (int i = 0; i < result.length; i++) {
        if (aptr <= middle && bptr <= end) {
            if (numbers[aptr] < numbers[bptr]) {
                result[i] = numbers[aptr];
                aptr++;
            }
            else {
                // (a[aptr], b[bptr]) is an inversion here
                count++;
                System.out.println("Found: (" + numbers[aptr] + "," + numbers[bptr] + "). If you print 'count' here it'll be one. See: " + count);
                result[i] = numbers[bptr];
                bptr++;
            }
        }
        else if (aptr > middle) {
            result[i] = numbers[bptr];
            bptr++;
        }
        else if (bptr > end) {
            result[i] = numbers[aptr];
            aptr++;
        }

    }

    for (int i = 0; i < result.length; i++) {
        numbers[begin + i] = result[i];
    }

    return count;

}

我调用计数设置为零的方法：findInversions(0, numbers.length - 1, 0)。

显然，问题在于count它不能在不同的递归中保持其价值。这是 Java，所以我不需要用 & 号传递它，我什至在mergeAndCount(). 那么这里有什么问题呢？

4

0 回答 0