字符串合并排序得到空指针异常？

Question

void MERGE(String[]A, int p, int q, int r)  {
    int n1 = q - p + 2;
    int n2 = r - q + 1;

    String[] L = new String[n1];
    String[] R = new String[n2];

    int i,j;

    for (i = 0; i < L.length; i++) {
        L[i] = A[p+i];
    }
    for (j = 0; i < R.length; j++) {
        R[j] = A[q+j+1];
    }

    L[n1-1] = "";
    R[n2-1] = "";

    i = 0;
    j = 0;

    for (int k = p; k <= r; k++) {
        if (L[i].compareToIgnoreCase(R[j]) < 0) {
            A[k] = L[i];
            i++;
        }
        else {
            A[k] = R[j];
            j++;
        }
    }
}
public void MERGE_SORT(String[] A, int p, int r) {

    if (p < r) {
        int q = (p+r)/2;

        MERGE_SORT(A, p, q);
        MERGE_SORT(A, q+1, r);
        MERGE(A, p, q, r);
    }

}

这个算法最初是针对整数的，所以我将其更改为对字符串进行排序。我得到一个 NullPointerException。问题似乎出在 compareToIgnoreCase() 行。这甚至是您为字符串实现合并排序的方式吗？

public static void main(String[] args) {
    String[] sA = {"Jack", "John", "Mike", "Moss", "Xo"};       
    Sort ob = new Sort();
    ob.MERGE_SORT(sA, 0, sA.length - 1);
}

Answer 1

方法 MERGE 中的第二个 for 循环使用了错误的变量 i（而不是 j）来检查上限 (i < R.length)。应该是：

for (j = 0; j < R.length; j++) {
    R[j] = A[q+j+1];
}

除此之外，代码中还有两个问题：

(1) 初始化L和R的for循环应该分别运行 L.length - 1 R.length - 1:

for (i = 0; i < L.length - 1; i++) {
    L[i] = A[p + i];
}
for (j = 0; j < R.length - 1; j++) {
    R[j] = A[q + j + 1];
}

(2) 您在 L 和 R 的最后位置使用了一个哨兵来保证合并 for 循环永远不会超过数组。这个哨兵应该大于数组中的最大可能值。在 int[] 的情况下，这可能是 Integer.MAX_VALUE （它与最大可能的元素一样大，但这可能是可以接受的）。但是由于您有 String 的数组，因此您需要尽可能大的 String 值。您正在使用空字符串 ("")，它是最小的 String:

L[n1 - 1] = "";
R[n2 - 1] = "";

为了测试，您可以使用 "ZZZ" 之类的东西，但您应该重写合并算法以在没有哨兵的情况下工作：

L[n1 - 1] = "ZZZ";
R[n2 - 1] = "ZZZ";

字符串合并排序得到空指针异常？

Merge sort for string getting null pointer exception?

java

mergesort