RadixSort算法運行時間

所以我有一個任務，我必須在大量隨機生成的列表上運行不同的排序算法。然後，我必須提交一份比較各種算法運行時間的報告。到目前爲止，我已經寫了3種排序算法的代碼：quicksort，mergesort和heapsort。我只剩下基數。以下是代碼。此代碼扔我一個ArrayIndexOutOfBoundsException在這條線：RadixSort算法運行時間

b[--bucket[(a[i]/exp) % 10]] = a[i];

，但我不能完全弄清楚如何改變代碼，使其正確的。

import java.util.*; 


public class RadixSort { 

    public static void main(String[] args) { 
     Random generator = new Random(System.currentTimeMillis()); 
     Scanner scan = new Scanner(System.in); 
     int size = scan.nextInt(); 
     int[] x = new int[size]; 

     long start = System.currentTimeMillis(); 

     for (int i = 0; i < size; i++) 
      x[i] = getRandomNumberInRange(0, 100); 

     radixSort(x); 
     System.out.println(Arrays.toString(x)); 
     long runtime = System.currentTimeMillis() - start; 
     System.out.println("Runtime: " + runtime); 
    }  

    private static int getRandomNumberInRange(int min, int max) { 
     if (min >= max) 
      throw new IllegalArgumentException("max must be greater than min"); 

     return (int)(Math.random() * ((max - min) + 1)) + min; 
    } 

    public static void radixSort(int[] a) { 
     int i, m = a[0], exp = 1, n = a.length; 
     int[] b = new int[10]; 

     for (i = 1; i < n; i++) 
      if (a[i] > m) 
       m = a[i]; 

     while (m/exp > 0) { 
      int[] bucket = new int[10]; 

      for (i = 0; i < n; i++) 
       bucket[(a[i]/exp) % 10]++; 
      for (i = 1; i < 10; i++) 
       bucket[i] += bucket[i - 1]; 
      for (i = n - 1; i >= 0; i--) 
       b[--bucket[(a[i]/exp) % 10]] = a[i]; 
      for (i = 0; i < n; i++) 
       a[i] = b[i]; 
      exp *= 10;   
     } 
    }  
}

來源

2016-10-02 Kj45

這不完全是基數排序的工作原理。每個桶應該有一個整數數組，然後在每個數字的主數組中重新組合。 –

我不想給整個解決方案，所以你可以更好地學習。但這是暗示：您的存儲桶應該聲明爲ArrayList [10]存儲桶;在桶[數字]你必須把數字除以exp得出最後一位數字。 –

你也可以保留你的解決方案，但你必須給b數組的大小等於a.length –

它發生，因爲你已經明確定義int[] b數組的固定大小：

int[] b = new int[10];

這就是它在溢出情況下，輸入比10大的原因。

將其從參數更改爲數組的可變長度。

int[] b = new int[a.length];

而且我建議你修復輸入的號碼只得到在區間(0; n>。

來源

2016-10-02 15:23:04

RadixSort算法運行時間

回答

相關問題