C#桶排序算法出现索引越界错误，求问题定位与解决

我来帮你定位这个问题的根源，先看代码里的几个关键部分：

核心问题：桶编号计算逻辑错误 #

你的GetBucketNumber方法直接返回value * 10，但你只通过InitializeBuckets初始化了10个桶（索引范围是0-9）。举个例子：

• 如果待排序数组里有值为1的元素，计算出的桶编号是10，这时候访问buckets[10]就会直接抛出索引越界异常，因为你的桶列表最大索引只有9
• 如果数组里有负数（比如-1），计算出的桶编号是-1，同样会触发索引越界

桶排序的核心是根据数据的实际范围合理划分桶，而不是简单的对值做乘法。

其他潜在问题 #

• 没有处理空数组的情况：如果输入的unsortedSequence是空数组，后续的排序逻辑可能会触发额外错误
• 固定桶数量不符合数据分布：如果你的数据范围很大（比如0-1000），固定10个桶会导致单个桶元素过多，失去桶排序的效率优势

修正后的代码示例 #

我调整了桶编号的计算逻辑，同时根据数据动态初始化桶的数量，适配任意范围的整数输入：

public int[] Sort(int[] unsortedSequence) {
    // 处理空数组的边界情况
    if (unsortedSequence.Length == 0) 
        return unsortedSequence;

    // 获取数据的范围，用于动态划分桶
    int minValue = unsortedSequence.Min();
    int maxValue = unsortedSequence.Max();
    
    // 每个桶覆盖10个整数的范围，计算需要的桶数量
    int bucketCount = (maxValue - minValue) / 10 + 1;
    List<List<int>> buckets = new List<List<int>>();
    InitializeBuckets(buckets, bucketCount);
    
    // 分散元素到桶中，传入最小值用于计算正确的桶编号
    Scatter(unsortedSequence, buckets, minValue);

    // 排序每个桶并合并结果
    int currentIndex = 0;
    foreach (List<int> bucket in buckets) {
        int[] sortedBucket = bucket.ToArray();
        InsertionSort(sortedBucket);
        foreach (int num in sortedBucket) {
            unsortedSequence[currentIndex++] = num;
        }
    }

    return unsortedSequence;
}

private static void Scatter(int[] array, List<List<int>> buckets, int minValue) {
    foreach (int value in array) {
        // 根据最小值偏移计算桶编号，确保编号落在0到bucketCount-1之间
        int bucketNumber = (value - minValue) / 10;
        buckets[bucketNumber].Add(value);
    }
}

private static void InsertionSort(int[] array) {
    int j;
    int temp;
    for (int i = 1; i < array.Length; i++) {
        j = i;
        while (j > 0 && array[j] < array[j - 1]) {
            temp = array[j];
            array[j] = array[j - 1];
            array[j - 1] = temp;
            j--;
        }
    }
}

private static void InitializeBuckets(List<List<int>> buckets, int count) {
    for (int i = 0; i < count; i++) {
        buckets.Add(new List<int>());
    }
}

关键修正点说明 #

1. 动态计算桶数量：根据输入数据的最小值和最大值，计算需要的桶数，确保每个桶的元素数量相对均衡
2. 修正桶编号计算：通过(value - minValue) / 10把所有值映射到非负的桶编号范围内，彻底避免索引越界
3. 增加边界处理：空数组直接返回，避免后续计算出错

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