试图做 mergeSort，索引越界

Question

我正在尝试进行合并排序。当我运行测试时。它说我的索引超出范围。我有没有漏掉什么错误？

错误是：java.lang.ArrayIndexOutOfBoundsException: Index 3 out of bounds for length 3

public static void mergeSort(int[] a) {
    int[] L = null; 
    int[] R = null; 

    if (a.length < 2)
        return;
    L = new int[a.length / 2];
    R = new int[a.length - a.length / 2];
    int x = 0;
    for (int y = 0; y < a.length; y++) {
        if (y < a.length) {
            L[y] = a[y];
        } else {
            R[x] = a[y];
            x += 1;
        }
    }
    mergeSort(L);
    mergeSort(R);
    merge(a, L, R); 
}

public static void merge(int[] a, int[] L, int[] R) {
    tracker.calltracking(a, L, R);
    int x = 0, y = 0, z = 0;
    while (x < L.length && y < R.length) {
        if (L[x] < R[y]) {
            a[z++] = L[x++];
        } else {
            a[z++] = R[y++];
        }
    }
    while (x < L.length) {
        a[z++] = L[x++];
    }
    while (z < R.length) {
        a[z++] = R[y++];
    }
}

Answer 1

让我们用长度为 3 的 a 调试 mergeSort 方法。

L初始化为1，R初始化为2

您将进入循环。

第一次迭代：y为0，y小于a.length

第二次迭代：y为1，y小于a.length。哎呀！索引 1 中的 L 是 OutOfBounds。

Answer 2

复制循环中的测试不正确：您将所有元素复制到 L 数组，该数组应该只接收左半部分。

与其在每次迭代时都进行测试，不如使用 2 个单独的循环：

public static void mergeSort(int[] a) {
    if (a.length >= 2) {
        int nL = a.length / 2;
        int nR = a.length - nL;
        int[] L = new int[nL];
        int[] R = new int[nR];

        for (int x = 0; x < nL; x++) {
            L[x] = a[x];
        }
        for (int x = 0; x < nR; x++) {
            L[x] = a[nL + x];
        }
        mergeSort(L);
        mergeSort(R);
        merge(a, L, R);
    }
}

试图做 mergeSort，索引越界

Trying to do the mergeSort, and the index out of bounds

java

mergesort