java - arrayoutofbounds 异常 - 合并排序 (CLRS)

Question

我正在尝试在java中实现合并排序，并且我已经按照CLRS书中给出的算法编写了代码。当我尝试运行代码时，我继续遇到数组越界异常。老实说，我不明白我在这里犯了什么错误。

package mergesort;
public class MergeSort {

    public static void MergeSort(int [] input, int low, int high){
        if(low<high){
            int mid=(low+high)/2;
            MergeSort(input,low,mid);
            MergeSort(input,mid+1,high);
            Merge(input,low,mid,high);
        }
    }

    public static void Merge(int [] input, int p, int q, int r){

    int n1=q-p+1,n2=r-q;
    int [] L=new int[n1+1];
    int [] R=new int[n2+1];
    for(int i=1;i<=n1;i++){
        L[i]=input[p+i-1];
    }
    for(int j=1;j<=n2;j++){
        R[j]=input[q+j];
    }
    L[n1+1]=-1;
    R[n2+1]=-1;
    int i=1;
    int j=1;
    for(int k=p;k<=r;k++){
        if(L[i]<=R[j]){
            input[k]=L[i];i++;
        }
        else{
            input[k]=R[j];j++;
        }
    }
    }

    public static String arrayToString(int[]input){
        String print="";
        for(int v:input){
            print +=v + " ";
        }
    return print;
    }

    public static void main(String[] args) {

        int input[]={1122,432,13,223,653,8233,7,2210};

        System.out.println(arrayToString(input));
      MergeSort(input,0,(input.length-1));
      System.out.println(arrayToString(input));

    }
}

Answer 1

int [] L=new int[n1+1];
L[n1+1]=-1; // this throws IndexOutOfBoundsException 
int [] R=new int[n2+1];
R[n2+1]=-1; // throws IndexOutOfBoundsException

您正在声明一个长度为 n1+1 的数组。这意味着数组从 0 到 n1。

尝试关注Java code conventions ，方法也以小写变量名称开头。使用声明性变量 p q r 很难理解它们是什么。代码必须是人类能够理解的。