java - 字符串合并排序出现空指针异常？

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值(value)。您正在使用空字符串 ( "" )，这是可能的最小的 String :

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

为了进行测试，您可以使用类似 "ZZZ" 的内容，但是您应该重写合并算法以在没有哨兵的情况下工作:

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