Java 合并排序递归奇怪

Question

我正在复习排序算法，因为它们在我的现实生活中并不经常出现，而这个让我发疯。我也有一段时间没有完成 Java，所以我想也许我忘记了一些 esotarica 语言，但我不这么认为。

我发现成功或失败取决于我如何进行递归调用以拆分数组。因此，如果我使用拆分调用的 return 值作为合并调用的参数，它就可以工作。但是，如果我先递归调用 split，然后调用 merge，它就会失败。但是，在我看来，它们都应该起作用。这似乎与堆栈的展开方式有关，但我不能完全理解它。

static Comparable[] mergesort(Comparable[] src) {
    if (src.length < 2)
        return src;

    int middle = src.length / 2;
    if (src.length % 2 > 0)
        middle++;

    Comparable[] left = new Comparable[src.length / 2];
    Comparable[] right = new Comparable[middle];

    System.arraycopy(src, 0, left, 0, left.length);
    System.arraycopy(src, src.length / 2, right, 0, right.length);

    // THIS DOESN'T WORK, BUT I DON'T KNOW WHY
    // mergesort(left);
    // mergesort(right);
    // return mergearrays(left, right);
    // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    // 
    // THIS ONE DOES WORK
    // 
    return mergearrays(mergesort(left), mergesort(right));
}

static Comparable[] mergearrays(Comparable[] left, Comparable[] right) {

    Comparable[] retval = new Comparable[left.length + right.length];

    int i = 0, j = 0, k = 0;
    for (; i < left.length && j < right.length;) {
        if (left[i].compareTo(right[j]) >= 0) {
            retval[k++] = right[j++];
        } else
            retval[k++] = left[i++];

    }

    while (k < retval.length) {
        if (i < left.length) {
            retval[k++] = left[i++];
        }
        if (j < right.length) {
            retval[k++] = right[j++];
        }
    }

    return retval;
}

Answer 1

您的 mergearrays 方法创建一个新数组，其中存储合并后的排序数组。因此，如果您不使用由 mergesort(left) 和 mergesort(right) 编辑的数组 return（它们本身是由先前调用 mergearrays 创建的数组），您将丢弃已排序的数组并将未排序的数组（left 和 right）传递给 mergearrays.

因此这段代码是错误的：

mergesort(left); // returns a new sorted array which you ignore, doesn't modify left
mergesort(right); // returns a new sorted array which you ignore, doesn't modify right
return mergearrays(left, right); // merges two unsorted arrays, and therefore is wrong

虽然这段代码是正确的：

// merges the two sorted arrays returned by mergesort(left) and mergesort(right)
return mergearrays(mergesort(left), mergesort(right));

一些合并排序实现在原始数组上执行合并步骤（即它们对数组进行排序而不是 return 排序新数组），在这种情况下 mergearrays 方法都不是mergesort 也不需要 return 任何东西，以下可以工作：

mergesort(left);
mergesort(right);
mergearrays(left, right);

Java 合并排序递归奇怪

Java merge sort recursion strangeness

java

recursion

mergesort