合并排序输出未完全排序

Question

我正在尝试使用 Java 实现“算法简介”书中的合并排序算法，但是当我执行代码时，我输出了半排序的：

input  = 2,4,5,1,2,3,6,7
output = 2,2,3,4,5,1,2,7 

public class Main {

    public static void main(String[] args) {
        int A[] = {
            2, 4, 5, 1, 2, 3, 6, 7
        };

        int B[] = new Main().mergeSort(A, 0, A.length);
        for (int i = 0; i < B.length; i++) {
            System.out.println(B[i]);
        }
    }

    void merge(int A[], int p, int q, int r) {
        int n1 = q - p + 1;
        int n2 = r - q;
        System.out.println("-n1: " + n1 + " n2: " + n2);
        int L[] = new int[n1];
        int R[] = new int[n2];


        for (int i = 0; i < n1; i++) {

            L[i] = A[p + i];
            System.out.println("L--|" + L[i]);
        }
        for (int j = 0; j < n2; j++) {
            R[j] = A[q + j];
            System.out.println("R--|" + R[j]);
        }

        int i = 0;
        int j = 0;

        for (int k = p; k < r; k++) {
            if (L[i] <= R[j]) {

                A[k] = L[i];
                System.out.println("A--|" + A[k] + " i: " + i);
                i = i + 1;
            } else {

                A[k] = R[j];
                System.out.println("A--|" + A[k] + " j: " + j);
                j = j + 1;
            }

            if (i == L.length || j == R.length) break;
        }
    }

    int[] mergeSort(int A[], int p, int r) {
        if (p < r) {
            int q = (int) Math.floor((p + r) / 2);
            mergeSort(A, p, q);
            mergeSort(A, q + 1, r);
            System.out.println("q: " + q + " p: " + p + " r:" + r);
            merge(A, p, q, r);
        }
        return A;
    }
}

如果有人可以在这段代码中帮助我，我将不胜感激。我知道 Java 中有很多现成的实现，在这种形式下，我只想知道我的代码出了什么问题。

Answer 1

不要使用 printf() 进行调试。它可以帮助您了解发生了什么，但可以设置断点并使用调试器。这将为您清除它，但这里有一些您可以立即执行的建议：

1. 不要将变量命名为 p、q、r 等。将它们重命名为“high”、“low”、“middle”。将“n1”重命名为 leftLen 等。这极大地提高了其他程序员的可读性，并帮助您了解发生了什么。

2. 想想你的程序在做什么。您的“mergeSort()”完全是标准的，因此问题必须出在您的合并程序中。不要运行 mergeSort，而是单独运行 merge 并查看发生了什么。尝试了解您的合并程序是如何工作的，并比较您认为它正在做什么。

3. 具体来说，考虑您的 L[] 和 R[]。它们会是空的吗？如果是这样，会发生什么？

4. 重复项怎么办？你能在左右数组中存储相同的数字吗？这会影响您的代码吗？

5. 有没有更好的方法来存储数字范围？

祝你好运！

Answer 2

感谢您的建议，我设法使其工作如下所示。

void merge(int A[], int low, int mid, int high) {
    int leftN = mid - low + 1;
    int rightN = high - mid;
    System.out.println("n1: " + leftN + " n2: " + rightN + " q: " + mid + " p: " + low + " r:" + high);
    int L[] = new int[leftN + 1];
    int R[] = new int[rightN + 1];

    L[leftN] = Integer.MAX_VALUE;
    R[rightN] = Integer.MAX_VALUE;

    for (int i = 0; i < leftN; i++) {

        L[i] = A[low + i - 1];
        System.out.println("L--|" + L[i]);
    }
    for (int j = 0; j < rightN; j++) {
        R[j] = A[mid + j];
        System.out.println("R--|" + R[j]);
    }

    int i = 0;
    int j = 0;

    for (int k = low - 1; k < high; k++) {

        if (L[i] <= R[j]) {

            A[k] = L[i];
            System.out.println("A--|" + A[k] + " i: " + i + " R[i] " + L[i]);
            i++;
        } else {

            A[k] = R[j];
            System.out.println("A--|" + A[k] + " j: " + j + " R[j] " + R[j]);
            j++;
        }
    }

}

int[] mergeSort(int A[], int low, int high) {
    if (low < high) {

        int mid = (low + high) / 2;
        System.out.println("q: " + mid + " p: " + low + " r:" + high);
        mergeSort(A, low, mid);
        mergeSort(A, mid + 1, high);
        merge(A, low, mid, high);

    }

    return A;
}