0

我正在尝试实现这个版本的合并排序，如 Cormen 的算法介绍中所见。

public static void merge(int[] A, int p, int q, int r) {
    int lengthOfLeftSubarray = q - p + 1;
    int lengthOfRightSubarray = r - q;

    int[] L = new int[lengthOfLeftSubarray + 1];
    int[] R = new int[lengthOfRightSubarray + 1];

    for(int i=0; i<lengthOfLeftSubarray; i++) 
        L[i] = A[p + i];

    for(int i=0; i<lengthOfRightSubarray; i++) 
        R[i] = A[q + i];

    L[lengthOfLeftSubarray] = -1;
    R[lengthOfRightSubarray] = -1;

    int i = 0, j = 0;
    for(int k=p; k<r; k++) {
        if(L[i] <= R[j]) {****
            A[k] = L[i];
            i++;
        }
        else {
            A[k] = R[j];
            j++;
        }
    }
}

public static void mergesort(int[] A, int p, int r) {
    if(p < r){
        int q = (p + r) / 2;
        mergesort(A, p, q);
        mergesort(A, q + 1, r);
        merge(A, p, q, r);
    }       
}

public static void main(String[] args) {
    int[] unsorted = {12, 16, 4, 2, 7, 6};
    Sorting.mergesort(unsorted, 0, unsorted.length - 1);
    System.out.println(Arrays.toString(unsorted));
}

我有两个问题：

  1. 书中提到了一张哨卡，它应该是某种特殊的值，可以放入一个数组中，不会干扰排序。我使用了 -1 ，因为我想不出一种使用infinite的方法，正如书中所建议的那样。谁能解释一下什么是哨兵？
  2. 代码在方法中抛出 ArrayOutOfBounds 异常merge，其中四颗星是 ( * *)。关于为什么会发生这种情况的任何想法？
4

1 回答 1

0

粗略一看（即我没有修复代码并在本地运行以确认测试用例有效），看起来有两个错误：

1) 

for(int i=0; i<lengthOfRightSubarray; i++) 
    R[i] = A[q + i];

正确的子数组应该q + 1像你进行递归调用时一样开始：

mergesort(A, q + 1, r);

2）在 OP 评论中，您似乎已经解决了这个问题，但是您选择的哨兵值不起作用。哨点值的点取决于算法。在这种情况下，标记值的意义在于它应该大于输入数组中的任何元素unsorted。特别是，当您这样做时，merge重点是您有两个已排序的子数组，并希望将它们合并为一个更大且仍是已排序的数组。这么简单的例子：

---- At the beginning ----
LEFT: {4, 12 16, INFINITY}
       ^
RIGHT: {2, 6, 7, INFINITY}
        ^
MERGED ARRAY: { }
               ^

---- After one iteration of the for loop ----
LEFT: {4, 12 16, INFINITY}
       ^
RIGHT: {2, 6, 7, INFINITY}
           ^
MERGED ARRAY: {2}
               ^

---- After second iteration of the for loop ----
LEFT: {4, 12 16, INFINITY}
          ^
RIGHT: {2, 6, 7, INFINITY}
           ^
MERGED ARRAY: {2, 4}
                  ^

---- After third iteration of the for loop ----
LEFT: {4, 12 16, INFINITY}
          ^
RIGHT: {2, 6, 7, INFINITY}
              ^
MERGED ARRAY: {2, 4, 6}
                     ^

---- After fourth iteration of the for loop ----
LEFT: {4, 12 16, INFINITY}
          ^
RIGHT: {2, 6, 7, INFINITY}
                 ^
MERGED ARRAY: {2, 4, 6, 7}
                        ^

你可以看到为什么哨兵值在这里很重要。由于右索引指向INFINITY，左子数组中的元素将被适当地合并。很容易-1替换INFINITY并监视您的merge触发器ArrayOutOfBounds异常。

哨兵值有用的全部原因仅仅是因为我们不想处理一个子数组用完值的情况。您可以轻松地实现该算法并检查 a 子数组何时用完元素（此时您只需用其他子数组的其余部分填充它），但它稍微不那么干净且难以推理。放置一个哨兵值可确保两个子数组都不会用完元素，这使您可以以更简单的方式编写证明（算法有效！）。

于 2013-09-08T02:56:47.177 回答