3

我对合并排序算法中的合并方法有疑问。我从http://algs4.cs.princeton.edu/22mergesort/Merge.java.html复制了以下代码。我无法理解为什么我们需要复制正确的子数组。

这个说法

if (i > mid) index[k] = aux[j++];

将右子数组复制到右子数组上。所以它基本上会覆盖相同的值。我觉得如果我越过了中线

  1. 左子数组值是完全排序的。
  2. 右子数组也排序到 j。
  3. j（包括 j）之后的所有条目都已排序，并且辅助数组和原始数组（a）具有相同的条目。

所以看起来我们可以取消复制到右子数组的语句，如果我已经越过了中间。

或者，也许我错过了一个用例。如果你能弄清楚，请告诉我。

// code begins

private static void merge(Comparable[] a, int[] index, int[] aux, int lo, int mid, int hi) {

    // copy to aux[]
    for (int k = lo; k <= hi; k++) {
        aux[k] = index[k]; 
    }

    // merge back to a[]
    int i = lo, j = mid+1;
    for (int k = lo; k <= hi; k++) {
        if      (i > mid)                    index[k] = aux[j++];
        else if (j > hi)                     index[k] = aux[i++];
        else if (less(a[aux[j]], a[aux[i]])) index[k] = aux[j++];
        else                                 index[k] = aux[i++];
    }
}
4

1 回答 1

1

我相信您是正确的-正是由于您指出的原因，该复制步骤似乎确实没有必要。

这可能是旧版本的合并函数的产物，其中要排序的两个数组未在输入数组中彼此相邻存储。如果输入数组存储在两个独立的数组中，则必须有一个最后的复制步骤，以便在另一个数组耗尽后将所有未使用的元素从一个数组移动到结果数组中。由于元素存储在输入数组中的方式，您可能不需要此步骤是正确的。

希望这可以帮助！

于 2013-06-06T18:32:24.387 回答