java - 对向后排序的数组使用桶排序时，程序会抛出 ArrayIndexOutOfBoundsException

问题描述

我需要通过桶排序运行一个向后排序的数组（IE 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)

（我标出了上面提到的行）

谁能帮我弄清楚为什么会这样？从 PRIME LOOP 1 到 PRIME LOOP 2 发生了什么变化，导致存储桶排序中出现 ArrayIndexOutOfBoundsException，我该如何解决？

标签： javaarrayssorting

java - 对向后排序的数组使用桶排序时，程序会抛出 ArrayIndexOutOfBoundsException

问题描述

解决方案

推荐阅读