基数排序和计数排序

我现在正在进行计数排序的基数排序。我想我已经在很大程度上理解和遵循的伪代码，但我得到一个数组越界错误：基数排序和计数排序

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; 
    } 
}

来源

2013-02-28 shinjuo

你是不是增加学家这可能是一个错字：

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

尝试：

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

来源

2013-02-28 20:44:26

好吧然后我回到了上面发布的超出界限的错误。 – shinjuo 2013-02-28 20:56:17

哪条线是47？ – 2013-02-28 21:11:27

对不起，它在这里 for（int m = 0; m shinjuo 2013-02-28 21:16:39

在线路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 []被声明时，它被声明为一个le ngth 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-28 21:22:15

基数排序和计数排序

回答

相关问题