基數排序和計數排序

我現在正在進行計數排序的基數排序。我想我已經在很大程度上理解和遵循的僞代碼，但我得到一個數組越界錯誤：基數排序和計數排序

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

基數排序和計數排序

回答

相關問題