程序在向后排序的数组上使用桶排序时抛出一个ArrayIndexOutOfBoundsException

Question

我需要运行一个向后排序的数组(即100，99，98，97 )。。。。3，2，1，0，从最高到最低)通过桶排序，将其排序最低到最高。生成数组的代码如下所示：

int n = 100;//Decides how large the arrays fed to the sorts are, minimum value of 100
int k = n - 1;
int howMany = 10;//Decides how many times the sorts are timed whenever the program is run
int[] baseArray = new int[n];

        //Loops entire thing as many times as howMany dictates, will refer to it as PRIME LOOP
        for (int m = 0; m < howMany; m++) { 

                  for (int i = 0; i < n; i++) //Generates array that's sorted backwards
                    {
                          baseArray[i] = k;
                          k--;
                    }

            int[] bucketArray = new int[n];

            for (int i = 0; i < n; i++) {
                bucketArray[i] = baseArray[i];
            }

            bucketSort(bucketArray); //Sends the array to bucket sort (This is line 218)**************
        }

下面是实际的桶类：

    //Bucket Sort
    public static void bucketSort(int[] input) {
        // get hash codes
        final int[] code = hash(input);
        
        // create and initialize buckets to ArrayList: O(n)
        List<Integer>[] buckets = new List[code[1]];
        for (int i = 0; i < code[1]; i++) {
          buckets[i] = new ArrayList();
        }
        
        // distribute data into buckets: O(n)
        for (int i : input) {
          buckets[hash(i, code)].add(i); //This is line 349*******************************************
        }
        
        // sort each bucket O(n)
        for (List bucket : buckets) {
          Collections.sort(bucket);
        }
        
        int ndx = 0;
        // merge the buckets: O(n)
        for (int b = 0; b < buckets.length; b++) {
          for (int v : buckets[b]) {
            input[ndx++] = v;
          }
        }
      }

      private static int[] hash(int[] input) {
        int m = input[0];
        for (int i = 1; i < input.length; i++) {
          if (m < input[i]) {
            m = input[i];
          }
        }
        return new int[] { m, (int) Math.sqrt(input.length) };
      }

      private static int hash(int i, int[] code) {
        return (int) ((double) i / code[0] * (code[1] - 1));
      }

当代码第一次通过for循环(素循环)桶排序时，会发出数组，并将其正确排序到最低到最高。但是，毫无疑问，当它第二次通过素数循环时，它给了我一个ArrayIndexOutOfBoundsException，具体来说，

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 18 out of bounds for length 10
    at SeniorResearch.Final_Project_Driver.bucketSort(Final_Project_Driver.java:349)
    at SeniorResearch.Final_Project_Driver.main(Final_Project_Driver.java:218)

(我划出了上面提到的几行)

有人能帮我弄清楚为什么会发生这种事吗？是什么导致桶排序中的ArrayIndexOutOfBoundsException从PRIME循环1更改为PRIME循环2，以及如何修复它？

Answer 1

在您的bucketSort方法中，您认为您正在使用final int[] code = hash(input);来计算桶数，但实际上，您正在计算数组的哈希数。

因此，您需要做的是计算数组元素的不同哈希代码的数量。

使用计算单个整数的散列的方法，然后计算得到多少不同的散列，然后将每个整数添加到“散列桶”中，等等.