使用Bucket Sort桶排序数组时出现ArrayIndexOutOfBoundsException报错如何解决

错误原因 #

• 数组下标越界直接诱因：bucketSort方法内层循环终止条件错误设置为i <= max，你的输入数组长度仅为15，但数组最大值为51，当循环变量i大于14时访问arr[i]就会触发越界异常。
• 逻辑错误：当前代码既不符合桶排序实现逻辑，也不是正确的计数排序实现，双重循环属于冗余设计。
• 返回值未接收：bucketSort方法返回了排序后的数组，但main方法调用时没有接收返回值，直接打印原数组无法得到排序结果。
• 计数逻辑缺陷：就算按计数排序思路实现，直接赋值sortedArray[currentVal] = currentVal的逻辑无法处理重复元素，且最终遍历结果会出现大量初始默认值0。

修正后的桶排序实现 #

package com.bucketsort;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        int[] arr = {20, 46, 22, 19, 6, 42, 14, 5, 48, 47, 17, 39, 51, 7, 2};

        System.out.println("Unsorted: " + Arrays.toString(arr));

        int[] sortedArr = bucketSort(arr);
        System.out.println("Sorted  :  " + Arrays.toString(sortedArr));
    }

    public static int[] bucketSort(int[] arr) {
        if (arr.length == 0) return arr;
        int max = getMax(arr);
        int min = getMin(arr);
        // 桶数量计算，这里按每个桶存5个元素计算，可根据场景调整
        int bucketCount = (max - min) / 5 + 1;
        ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(bucketCount);
        // 初始化桶
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }
        // 将元素分配到对应桶中
        for (int val : arr) {
            buckets.get((val - min) / 5).add(val);
        }
        // 每个桶内部排序，合并到结果数组
        int sortedIndex = 0;
        int[] sortedArr = new int[arr.length];
        for (ArrayList<Integer> bucket : buckets) {
            Collections.sort(bucket);
            for (int val : bucket) {
                sortedArr[sortedIndex++] = val;
            }
        }
        return sortedArr;
    }

    // 获取数组最大值
    public static int getMax(int[] arr) {
        int maxValue = arr[0];
        for(int i=1;i<arr.length;i++) {
            if(arr[i] > maxValue) {
                maxValue = arr[i];
            }
        }
        return maxValue;
    }
    // 新增获取数组最小值方法
    public static int getMin(int[] arr) {
        int minValue = arr[0];
        for(int i=1;i<arr.length;i++) {
            if(arr[i] < minValue) {
                minValue = arr[i];
            }
        }
        return minValue;
    }
}

运行结果 #

Unsorted: [20, 46, 22, 19, 6, 42, 14, 5, 48, 47, 17, 39, 51, 7, 2]
Sorted  :  [2, 5, 6, 7, 14, 17, 19, 20, 22, 39, 42, 46, 47, 48, 51]

内容的提问来源于stack exchange，提问作者RaVeN