java - 在 Java 中实现归并排序 : Only zeroes

Question

我正在尝试在 Java 中实现一些排序算法，将 int 数组作为一种教育过程。我目前正在尝试围绕合并排序进行思考。昨天我走得很远，结果是一个大小正确的数组，但只包含零。今天我从头开始，现在我被困在同一个点上。 ^^这是我的代码:

public static int[] mergeSort(int[] array) {
    if (array.length < 2) {
        return array;
    }
    int left = 0;
    int right = array.length;
    int p = array.length / 2;
    int[] lArray = Arrays.copyOfRange(array, left, p);
    int[] rArray = Arrays.copyOfRange(array, p, right);
    lArray = mergeSort(lArray);
    rArray = mergeSort(rArray);
    return merge(lArray, rArray);
}

private static int[] merge(int[] lArray, int[] rArray) {
    int[] result = new int[lArray.length + rArray.length];
    int idx = 0;
    int rIdx = 0;
    int lIdx = 0;
    while (lIdx < lArray.length - 1 && rIdx < rArray.length - 1) {
        if (lArray[lIdx] < rArray[rIdx]) {
            result[idx] = lArray[lIdx];
            lIdx++;
        } else if (lArray[lIdx] >= rArray[rIdx]) {
            result[idx] = rArray[rIdx];
            rIdx++;
        }
        idx++;
    }
    if (lIdx < (lArray.length - 1)) {
        result[idx] = lArray[lIdx + 1];
    } else if (rIdx < (rArray.length - 1)) {
        result[idx] = rArray[rIdx + 1];
    }
    return result;
}

我认为它的样式和可读性都很好。那么，所有算法和 Java 高手，我错过了什么？调试指向 merge 方法，但我不能完全确定它，所以我按原样发布它。

提前致谢!

Answer 1

我在您的 merge 方法中看到两个问题:

首先，您的 while 循环忽略了左右数组的最后一个元素。你应该改变

while (lIdx < lArray.length - 1 && rIdx < rArray.length - 1)

到

while (lIdx < lArray.length && rIdx < rArray.length)

其次，在那个 while 循环之后，您还需要两个 while 循环来添加左数组的尾部或右数组的尾部。相反，您只添加一个元素。

替换

if (lIdx < (lArray.length - 1)) {
    result[idx] = lArray[lIdx + 1];
} else if (rIdx < (rArray.length - 1)) {
    result[idx] = rArray[rIdx + 1];
}

与

while (lIdx < lArray.length) {
    result[idx++] = lArray[lIdx++];
} 
while (rIdx < rArray.length) {
    result[idx++] = rArray[rIdx++];
}