使用merge-sort理解fencepost处理的问题

Question

Fencepost (也称为off-by-one错误，也称为OBOB (off-by-one bug)。

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

我注意到某些版本的merge-sort需要MID值为(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;
}

Answer 1

第一个数组中的元素数是中间开始的+ 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, 10或myIntArray, 1, 9。

因此，假设我们传递了像myIntArray, 0, 9这样的参数，当我们有两个排序的子数组时，让我们看看mergeSort()的最后一个(折叠方向)调用：

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

mergeSort(integerArray, start, middle); where start =0和middle =4(包括索引从0到4的项目-都包括: 1,3,4,5,7)

和

开始=中间+1=4+1=5和结束=9(包括索引从5到9的数字-都包括: 0,2,11,12,12)。

这里

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

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

整个过程一直持续到我们得到可以考虑排序的大小为1的数组，然后我们开始合并-当然，你已经知道这一点。如您所见，这些变量- start、middle、end -是元素的位置(索引)，而不是元素的数量。

如果您将参数作为项的位置(如mergeSort(myIntArray, 0, 9); )，而不是项的数量，那么您发布的代码可以很好地工作。一开始应该是array.length() - 1希望它能帮上忙:)