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 行时，您将得到一个 ArrayOutOfBoundsException ，因为当 C[] 被声明时，它被声明为长度为 23 的数组，您只能从 0 到 22 进行索引。值的实际范围应包括 0 到最大值。

因此，您需要将 C[] 声明为int[] C = new int[d+1];或存储到 中的值 C[A[k]-1] = C[A[k]-1] + 1;，具体取决于您是否将零视为输入数组 sortNumbers 中的可接受值。

然而，问题和代码发生了变化。这段代码对这些值求和，并逐渐将它们添加到数组 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 回答