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算法运行时间

回答

相关问题