Java实现归并排序遇数组越界异常求助

兄弟，你遇到的数组越界问题根源不在辅助数组的长度计算上——r-l+1确实是当前要合并区间的元素总数，完全正确！问题出在原数组和辅助数组的索引映射关系上，你直接用原数组的索引去访问辅助数组，这就踩坑了！

错误原因拆解 #

举个例子：假设当前要处理的区间是l=3, r=5，那辅助数组helper的长度是5-3+1=3，它的有效索引只有0、1、2。但你写的循环：

for(int i=l; i<=r; i++){
    helper[i] = arr[i];
}

这里i从3开始，直接访问helper[3]，明显超出了helper的最大索引2，直接触发ArrayIndexOutOfBoundsException。

修正方案：索引映射转换 #

你需要把原数组的索引转换成辅助数组的相对索引——用i - l来对应helper的索引（原数组的l位置对应helper的0位置）。同时，后面比较helper元素的时候，也要同步转换索引。

修正后的merge方法代码 #

void merge(int arr[], int l, int m, int r) {
    // 辅助数组长度计算完全正确
    int helper[] = new int[r-l+1];
    // 修正索引：用i-l作为helper的索引
    for(int i=l; i<=r; i++){
        helper[i - l] = arr[i];
    }
    int i = l;
    int k = l;
    int j = m+1;
    // 比较时同样转换helper的索引
    while(i<=m && j<=r){
        if(helper[i - l] <= helper[j - l]){
            arr[k] = helper[i - l];
            i++;
        }else{
            arr[k] = helper[j - l];
            j++;
        }
        k++;
    }
    while(i<=m){
        arr[k] = helper[i - l];
        i++;
        k++;
    }
}

完整可运行代码 #

public class HelloWorld{
    public static void main(String []args){
        HelloWorld ms = new HelloWorld();
        int arr[] = new int[]{4,3,0,1,3,2,4,20,13,22,10};
        ms.sort(arr, 0, arr.length - 1);
        ms.printArr(arr);
    }
    void printArr(int arr[]) {
        int n = arr.length;
        for(int i = 0; i<n; i++){
            System.out.print(" "+arr[i]);
        }
    }
    void sort(int arr[], int l, int r) {
        if(l<r){
            int m = (l+r)/2;
            sort(arr, l, m);
            sort(arr, m+1, r);
            merge(arr, l, m, r);
        }
    }
    void merge(int arr[], int l, int m, int r) {
        int helper[] = new int[r-l+1];
        for(int i=l; i<=r; i++){
            helper[i - l] = arr[i];
        }
        int i = l;
        int k = l;
        int j = m+1;
        while(i<=m && j<=r){
            if(helper[i - l] <= helper[j - l]){
                arr[k] = helper[i - l];
                i++;
            }else{
                arr[k] = helper[j - l];
                j++;
            }
            k++;
        }
        while(i<=m){
            arr[k] = helper[i - l];
            i++;
            k++;
        }
    }
}

这样修改后，辅助数组只会占用当前合并区间所需的内存，既不浪费空间，也不会出现越界问题，不管原数组多大都能正常运行。

内容的提问来源于stack exchange，提问作者Victor Chen