0

我正在尝试在 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));

    }
}
4

2 回答 2

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 代码约定，方法以小写字母开头，变量名也是如此。使用声明性变量p q r很难理解它们是什么。代码必须为人类所理解。

于 2013-09-19T02:27:38.593 回答
0

假设数组中的Merge算法是基于 1 的。CLRS但是，Java 中的数组是从 0 开始的。

当我遇到这类问题时，我可能会做以下事情之一。

  1. 为每个数组再分配一个元素并丢弃第一个元素。像这样：

    int[] L = new int[n1 + 1 + 1]; // extra `+1`
int[] R = new int[n2 + 1 + 1]; // extra `+1`
// ...
int[] input = { 0, 1122, 432, 13, 223, 653, 8233, 7, 2210 }; // leading 0
MergeSort(input, 1, input.length - 1);

  2. 添加-1到每个数组访问。像这样：

    for(int i = 1; i <= n1; i++){
    L[i] = input[p + i - 1 - 1]; // extra `-1`
}
// ...
MergeSort(input, 1, input.length);
  3. 完全理解算法。没有技巧。这是建议的方法。
于 2013-09-19T03:00:46.227 回答