java中合并排序中的数组索引越界异常

Question

我在java中编写了这段用于合并排序的代码，其中我尝试仅使用一个辅助数组来使用合并排序。但它会导致数组越界异常。请帮我修复带有 1 个辅助数组的 mergeSort 的代码。

public static void mergeSort(int arr[], int s, int e){
        if(s < e){
            int mid = s + (e-s)/2;

            mergeSort(arr, s, mid);
            mergeSort(arr, mid+1, e);

            merge(arr, s, mid, e);
        }
    }

    public static void merge(int arr[], int s, int mid, int e){
        int arr2[] = new int[arr.length];
        for(int i = 0;i <= e; i++){
            arr2[i] = arr[i];
        }

        int i = 0, j = mid+1, k = s;

        while(i < mid+1 && j < e+1){
            if(arr2[i] < arr2[j])   arr[k++] = arr2[i++];
            else    arr[k++] = arr2[j++];
        }

        while(i < mid+1)    arr[k++] = arr2[i++];
        while(j < e+1)  arr[k++] = arr2[j++];
    }

Answer 1

您的代码中有一个微妙的错误。在 merge 方法中，您使用不同的索引来迭代 arr2 和 arr。这是 ArrayIndexOutOfBoundsException 的主要原因。

要修复代码，请注意以下几点：

从 arr 复制到 arr2 时，应该只复制 s 中的元素到 e，而不是整个数组。 对于 arr2，索引 i 和 j 应分别从 s 和 mid + 1 开始。

这是合并方法的更正版本：

public static void merge(int arr[], int s, int mid, int e){
    int arr2[] = new int[arr.length];
    for(int i = s; i <= e; i++){
        arr2[i] = arr[i];
    }

    int i = s, j = mid + 1, k = s;

    while(i <= mid && j <= e){
        if(arr2[i] < arr2[j]) arr[k++] = arr2[i++];
        else arr[k++] = arr2[j++];
    }

    while(i <= mid) arr[k++] = arr2[i++];
    while(j <= e) arr[k++] = arr2[j++];
}