0

从昨天开始，我一直在阅读一个合并排序示例（高效的示例），尽管查看了代码，但我仍然无法理解它是如何工作的：

private static void sort(int[] list) {
    a = list;
    int n = a.length;
    // according to variant either/or:
    b = new int[n];
    b = new int[(n + 1) / 2];
    mergesort(0, n - 1);
}

private static void mergesort(int first, int last) {
    if (first < last) {
        int mid = (first + last) / 2;
        mergesort(first, mid);
        mergesort(mid + 1, last);
        merge(first, mid, last);
    }
}

到目前为止，理解算法没有问题，但混淆在于以下方法：

private static void merge(int first, int mid, int last) {
    int i, j, k;

    i = 0;
    j = first;

    while (j <= mid)
        b[i++] = a[j++]; // *j's value is now mid*

    i = 0; // *i is reset to 0, nothing's been done to j*
    k = first;


    // *before entering the following while loop, j still carries mid's value*
    while (k < j && j <= last)
        if (b[i] <= a[j])
            a[k++] = b[i++];
        else
            a[k++] = a[j++];        

    // copy back remaining elements of first half (if any)
    while (k < j)
        a[k++] = b[i++];
}

进入第二个 while 循环while (k < j && j <= last)是我不明白这种排序是如何工作的。据我了解，数组的前半部分a已经复制到辅助数组中，现在我们想通过比较（后半部分）与辅助数组b来排列整个数组，以便我们可以得到较小的数组元素并放置它在数组中以升序对数组进行排序。a[j++]b[i++]a

但是为什么while (k < j && j <= last)？k < j听起来很合乎逻辑，因为我们需要从辅助数组中取回所有值，但为什么j <= last呢？为什么我们不能这样做while (k <= last)？

另外，有人可以确认我对上述代码中 j 值的理解是正确的吗？

4

1 回答 1

0

k < j 表示辅助数组b仍然包含元素

j <= last 表示a的第二部分仍然包含元素

我们不能在这里使用，因为当 j 变为 last+1 时，我们可能会访问超出边界的k <= last数组a索引

评论太长了，在这里补充：

当可用内存有限（大型数据集）时，此变体很有用。在一些教程中提到了它（我在 J.Bucknall 关于 Delphi 算法的书中遇到过它）。它是稳定的（ if (b[i] <= a[j]) 保持稳定。它通常不会更快，因为最好不要复制数据，但是，例如，'触发'源和目标数组（指针）在每个阶段

于 2013-04-13T11:08:09.780 回答