java - 线程 "main"java.lang.ArrayIndexOutOfBoundsException : 2 MergeSort 中的异常

Question

我正在尝试使用 eclipse IDE 在 Java 中实现 MergeSort 算法。 我收到以下错误

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 2

它包含三个方法:merge()、mergeSort() 和 printArray()

public class MergeSort {
    public static void main(String[] args) {
        int[] numbers = { 10, 5, 3, 7, 6, 2, 21, 4 };

        mergeSort(numbers);
        printArray(numbers);

    }

    public static int[] mergeSort(int[] A) {
        int n = A.length;

        if (n < 2) {
            return A;
        }
        int mid = n / 2;

        int[] left = new int[mid];
        int[] right = new int[n - mid];

        for (int i = 0; i < mid - 1; i++) {
            left[i] = A[i];
        }

        for (int i = mid; i < n - 1; i++) {
            right[i - mid] = A[i];
        }

        mergeSort(left);
        mergeSort(right);
        merge(left, right);
        return A;
    }

    public static int[] merge(int[] A, int[] B) {
        int[] C = new int[A.length + B.length];
        int i = 0;
        int j = 0;
        int k = 0;

        int nL = A.length;
        int nR = B.length;

        while (i < nL && j < nR) {
            if (A[i] <= B[j]) {
                C[k] = A[i];
                k = k + 1;
                i = i + 1;
            } else {
                C[k] = A[j];
                j = j + 1;
            }
            k = k + 1;
        }

        while (i < nL) {
            C[k] = A[i];
            i = i + 1;
            k = k + 1;
        }

        while (j < nR) {
            C[k] = B[j];
            j = j + 1;
            k = k + 1;
        }
        return C;
    }

    public static void printArray(int[] A) {
          for (int i = 0; i < A.length; i++) {
            System.out.println(A[i]);
          }
    }
}

Answer 1

merge() 方法中的第一个 while 循环有问题。您正在将 A[j] 分配给 C[k]，而它应该是 B[j]。此外，对于 if 条件，您将 k 递增两次。

将 while 循环更改为:

while (i < nL && j < nR) {
  if (A[i] <= B[j]) {
    C[k] = A[i];
    i = i + 1;
  } else {
    C[k] = B[j];
    j = j + 1;
  }
  k = k + 1;
}

但是，除了这个问题，您的代码还有其他问题。

首先，您的循环范围不正确。目前您缺少 (mid - 1)^th 和 (n - 1)^th 元素。将循环更改为:

for (int i = 0; i < mid; i++) {
    left[i] = A[i];
}

for (int i = mid; i < n; i++) {
    right[i - mid] = A[i];
}

其次，您的 mergeSort() 方法创建了一个新数组。您当前未使用返回值。将返回值分别重新分配给left和right:

left = mergeSort(left);
right = mergeSort(right);
return merge(left, right);

最后，您还需要将最终结果重新分配给 numbers 数组:

numbers = mergeSort(numbers);
printArray(numbers);