1

私は現在 InsertionSort と MergeSort を実装して操作を比較しています。以前に MergeSort を実装しましたが、現在のアルゴリズムの教科書でバージョンを試しています。コメントでマークされた行 (58 行目) で範囲外の配列エラーが発生しています。それを超えると、おそらく 60 行目でもエラーになると思います。これは T の本にあるアルゴリズムですが、見つかりません。私のエラーがどこから来たのか。コードには、テストするための単純な main メソッドが含まれています。完全なコードが含まれているため、コピー可能で実行可能です。

package algsortcomp;


public class AlgSortComp {


public static void InsertionSort(int[] data){
    //Sorts given array by Insertion Sort
    //Input: an array data of ints
    //Output: array data sorted in nondecreasing 
    int v, j;
    for (int i = 1; i<data.length; i++){
        v = data[i];
        j = i - 1;
        while (j >= 0 && data[j] > v){
            data[j+1] = data[j--];
        }
        data[j+1]=v;
    }
}

public static void MergeSort(int[] data){
    //Sorts array data by recursive mergesort
    //Input: an array data of ints
    //Output: array data sorted in nondecreasing order
    int dlen = data.length;
    int mid = dlen/2;

    int[] b = new int[mid];
    int[] c = new int[dlen-mid];

    if (dlen > 1){
       System.arraycopy(data, 0, b, 0, mid-1);
       System.arraycopy(data, mid, c, 0, dlen-mid);
       MergeSort(b);
       MergeSort(c);
       Merge(b, c, data);
   }         
}

public static void Merge(int[] b, int[] c, int[] data){
    //Merges two sorted arrays into one sorted array
    //Input: Arrays b and c both sorted
    //Output: Sorted array data of elements b and c.
    int p = b.length, q = c.length, dlen = data.length;
    int i=0, j=0, k=0;
    while (i<p && j<q){
        if (b[i] <= c[j])
            data[k] = b[i++];
        else
            data[k]=c[j++];
        k++;
    }
    if (i == p)
        System.arraycopy(c, j, data, k, dlen-1); //<---currently getting Array out of bounds here, tried replacing with
    else                                         //dlen-k and error is gone but array returned is all [0,0,...,0]
        System.arraycopy(b, i, data, k, dlen-1);
}



public static void main(String[] args) {
    int [] test = {3, 5, 23, 56, 1, 12, 32};
    String arraystr = java.util.Arrays.toString(test);
    System.out.println(arraystr);

    //InsertionSort(test);
    MergeSort(test);
    System.out.println(java.util.Arrays.toString(test));
}

}

クラスの誰もまだ起きていないので、謙虚な皆さんに、私のエラーを見つけるために余分な目をお願いします. 前もって感謝します。

編集：また、Arrays.toString（）だけでjava.util.Arrays.toString（）を呼び出す方法を忘れています。java.util.Arrays をインポートしようとしましたが、うまくいきませんでした。確かに、Java/arrays に触れてからかなり時間が経ちました。

4

1 に答える 1

1

System.arraycopyコピーする要素の数を最後のパラメーターとして受け取ります。ここで、c から残りのアイテムの数をコピーすると、qj になるはずです。同様に、次の場合の pi です。

あなたはラインのimport java.util.Arrays 後ですか？package

また、これSystem.arraycopy(data, 0, b, 0, mid-1);を

System.arraycopy(data, 0, b, 0, mid);

于 2013-03-09T16:37:18.590 に答える