0

現在、カウントソートを実装する基数ソートに取り組んでいます。ほとんどの場合、疑似コードを理解して従ったと思いますが、配列の範囲外エラーが発生しています。

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 12
    at RunRadixSort.radixSort(RunRadixSort.java:47)
    at RunRadixSort.main(RunRadixSort.java:15)

私のコード

import java.text.DecimalFormat;
    import java.util.Arrays;


   import java.text.DecimalFormat;
import java.util.Arrays;


public class RunRadixSort {


    public static void main(String[] args) {

        int[] sortNumbers = {4,5,6,2,3,7,2,1,23,5,13};
        int[] sorted = new int[sortNumbers.length];
        DecimalFormat df = new DecimalFormat("#.########");
        int max = getMax(sortNumbers);
        long timeStart = System.nanoTime();
        sorted = radixSort(sortNumbers, max);
        long timeEnd = System.nanoTime();
        long elapsedTime = timeEnd - timeStart;
        double time = (double)elapsedTime / 1000000;
        System.out.println(Arrays.toString(sorted));
        System.out.println("\nTotal Execution Time: " + df.format(time)+ " miliseconds");
    }

    public static int getMax(int[] A){
        int max = A[0];
        for(int i = 1; i < A.length; i++){
            if(A[i] > max){
                max = A[i];
            }
        }
        return max;
    }

    public static int[] radixSort(int[] A, int d){
        int[] B = new int[A.length];
        int[] C = new int[d + 1];
        for(int i = 0; i < d; i++){
            for(int k = 0; k < A.length; k++){
                C[A[k]]++;
            }
            int total = 0;
            for(int l = 0; l < d; l++){
                int temp = C[l];
                C[l] = total;
                total += temp;
            }
            for(int m = 0; m < A.length; m++){
                B[C[A[m]]] = A[m];
                C[A[m]]++;
            }
        }
        return B;
    }
}
4

2 に答える 2

1

jをインクリメントしていません。これはタイプミスの可能性があります。

 for(int j = 0; j < d; i++){

これを試して：

for(int j = 0; j < d; j++){
于 2013-02-28T20:44:26.860 に答える
0

行でfor(int j = 0; j < d; i++){

そのはずfor(int j = 0; j < d; j++){

また、C[A[k]] = C[A[k]] + 1; k=8およびA[K]= 23の場合、C []が宣言されると、0から22までのインデックスしか付けられない長さ23の配列として宣言されるため、ArrayOutOfBoundsExceptionが発生します。実際の値の範囲には、0から最大までが含まれている必要があります。

したがって、入力配列sortNumbersでゼロを許容値と見なすかどうかに応じて、C []をとして宣言するか、のint[] C = new int[d+1];値に格納する 必要があります。C[A[k]-1] = C[A[k]-1] + 1;

ただし、質問とコードは変更されました。このコードブロックは値を合計し、配列Cにますます追加します。

  for(int l = 0; l < d; l++){
            int temp = C[l];
            C[l] = total;
            total += temp;
        }

次に次のブロック

 for(int m = 0; m < A.length; m++){
            B[C[A[m]]] = A[m];
            C[A[m]]++;
        }

配列Cのエントリの値を配列Bのインデックスとして使用しますが、Bは配列Aと同じサイズです。

Cは、値の出現の合計ではなく、値の合計を保持する必要がありますか？

于 2013-02-28T21:22:15.673 に答える