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+1lengthの配列を宣言しています。これは、配列が 0 から n1 になることを意味します。

Java コードの規則に従うようにしてください。メソッドは変数名も小文字で始まります。宣言型変数の使用p q rは、それらが何であるかを理解するのが困難です。コードは人間が理解できるものでなければなりません。

于 2013-09-19T02:27:38.593 に答える
0

仮定配列のMergeアルゴリズムCLRSは 1 ベースです。ただし、Java の配列は 0 ベースです。

この種の問題に直面したとき、私は次のいずれかを行うことがあります。

  1. 各配列にもう 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 に答える