1

Fencepost (AKA An off-by-one error (OBOE)，通常也称为 OBOB (off-by-one bug)。

给定一个数组，我通常会遍历索引 0 到 array.length() （半开区间）。

我注意到某些版本的合并排序要求中间值为 (start+end)/2。当您计算合并过程中的元素数量时，我们有时将使用 (end - start) 作为元素数量或 (end - mid + 1)。我无法直观地得到这个？不知何故，我很难理解这一点，每次看到任何新的实现时都觉得自己在胡思乱想。

有人可以提供一种直观的方式来理解我如何应用/识别栅栏问题吗？这对于多维数组是否相同？

public static BigInteger mergeSort(int[] integerArray, int start, int end) {
    if (start >= end) { // less than equal to is important for cases when start = end = 0
        return BigInteger.valueOf(0);
    }
    int middle = (start + end) / 2;
    BigInteger numInv1 = mergeSort(integerArray, start, middle);
    BigInteger numInv2 = mergeSort(integerArray, middle + 1, end);
    BigInteger numInv3 = runMerge(integerArray, start, middle, end);
    return numInv1.add(numInv2).add(numInv3);
}

private static BigInteger runMerge(int[] integerArray,
                                   int start, int middle, int end) {
    BigInteger numInv = BigInteger.valueOf(0);
    int n1 = middle - start + 1;
    /*
    number of elements in 1st array is middle - start + 1. why ?
    */

    int n2 = end - middle;       // number of elements in 2nd array
    /*
    number of elements in 2nd array is end - middle. why ?
    */

    int []p = new int[n1];
    int []q = new int[n2];
    int i, j, k;
    for (i = 0; i < n1 ; i++) {
        p[i] = integerArray[start + i];
    }
    for (j = 0; j < n2; j++) {
        q[j] = integerArray[middle + j + 1];
        //Why do we do +1 here? because we use 2nd array for mid+1 till end elements
    }
    i = 0;
    j = 0;
    k = start;
    while ( i < n1 && j < n2) {
        if (p[i] <= q[j]) {
            integerArray[k++] = p[i++];
        } else {
            integerArray[k++] = q[j++];
            numInv = numInv.add(BigInteger.valueOf(n1-i));
        }
    }
    while ( i < n1 ) {
        integerArray[k++] = p[i++];
    }
    while ( j < n2 ) {
        integerArray[k++] = q[j++];
    }
    return numInv;
}
4

1 回答 1

0

第一个数组中的元素数是中间 - 开始 + 1。为什么？第二个数组中的元素数是结束 - 中间。为什么？

它们不是元素的数量，它们是将初始数组分解为更小的数组所需的元素的边缘索引。假设您有一个要排序的数组：

int[] myIntArray = {7,4,3,5,1,12,12,11,0,2};

它包含 10 个元素，但索引从 0 到 9。因此，在您的方法mergeSort(int[] integerArray, int start, int end);中，它应该是myIntArray, 0, 9，而不是myIntArray, 1, 10nor myIntArray, 1, 9。

所以，假设我们传递类似的参数，让我们看看当我们有两个排序子数组时myIntArray, 0, 9的最后一个（折叠方向）调用：mergeSort()

在计算出中间值 = (0 + 9) / 2 = 4 之后，我们将初始数组分解为 2 个数组，如下所示：

mergeSort(integerArray, start, middle);其中 start = 0 和 middle = 4（包括索引从 0 到 4 的项目 - 都包括：1、3、4、5、7）

和

mergeSort(integerArray, middle + 1, end);其中 start = middle + 1 = 4 + 1 = 5 和 end = 9（包括索引从 5 到 9 的数字 - 两者都包括：0、2、11、12、12）。

这里

q[j] = integerArray[middle + j + 1];

通过添加 +1，我们得到了第 5 个元素。请记住，当前调用变量 middle 的堆栈中等于 4，并且此值 (4) 被传递给runMerge(). 值middle + 1转到先前完成的调用之一mergeSort()。

整个过程一直持续到我们得到大小为 1 的数组，这些数组可以被认为是排序的，然后我们开始合并——当然，你已经知道了。如您所见，这些变量——开始、中间、结束——是元素的位置（索引）而不是元素的数量。

如果您将参数视为项目的位置mergeSort(myIntArray, 0, 9);而不是项目数，则您发布的代码可以正常工作。一开始应该是array.length() - 1希望它有帮助:)

于 2017-07-22T08:41:30.543 回答