在 Java 中实现归并排序：只有零

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- 破解，我错过了什么？调试指向合并方法，但我不能完全确定，所以我按原样发布。

提前致谢！

Answer 1

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

这部分有点奇怪。为什么只将一个剩余元素复制到结果数组中？您应该将所有剩余元素从 lArray 或 rArray 复制到您的结果中。使用 'while' 而不是 'if'.

Answer 2

我在您的 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++];
}

Answer 3

给你

public class MergeSort {

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);
    //printArray(lArray); seems ok
    //printArray(rArray); seems ok
    lArray = mergeSort(lArray);
    rArray = mergeSort(rArray);
    return merge(lArray, rArray);
}

private static int[] merge(int[] lArray, int[] rArray) {
    /*System.out.println("Ive got");
    printArray(lArray);
    printArray(rArray); seems ok*/
    int[] result = new int[lArray.length + rArray.length];
    int index = 0;
    int rightIndex = 0;
    int leftIndex = 0;
    while (leftIndex < lArray.length && rightIndex < rArray.length) { //TODO
        if (lArray[leftIndex] < rArray[rightIndex]) {
            result[index] = lArray[leftIndex];

            leftIndex++;
            index++;
            //} else if (lArray[leftIndex] >= rArray[rightIndex]) { // You don't have to check it!!!
        } else {
            System.out.println("2 left index " + leftIndex + " index " + index);
            result[index] = rArray[rightIndex];
            rightIndex++;
            index++;
        }
    }
    while (leftIndex < (lArray.length)) { // TODO
        result[index] = lArray[leftIndex];
        index++;
        leftIndex++;
    }
    while (rightIndex < (rArray.length)) { // TODO
        result[index] = rArray[rightIndex];
        index++;
        rightIndex++;
    }
    System.out.println("Returning ");
    printArray(result);
    return result;
}

public static void printArray(int[] arr) {
    for (int i : arr)
        System.out.print(i + " ");
    System.out.println();
}

public static void main(String[] args) {
    int[] arr = {2, 1, 3, 4, 0, -1};
    printArray(arr);
    arr = mergeSort(arr);
    printArray(arr);
}
}

错误的地方标有//TODO

在 Java 中实现归并排序：只有零

Implementing merge sort in Java: Only zeroes

java

sorting

algorithm

mergesort