为什么这段代码总会出现越界问题

Question

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> bucket_sort(vector<int> arr, int size, int count)
{
    int new_size = count / size + 1;
    vector<vector<int>> bucket(new_size);
    for (int i = 0; i < size; i++) {
        bucket[arr[i] / 10].push_back(arr[i]);
    }

    int k = 0;
    for (int i = 0; i < new_size; i++) {
        sort(bucket[i].begin(), bucket[i].end());
        for (int j = 0; j < bucket[i].size(); j++) {
            arr[k++] = bucket[i].at(j);
        }
    }
    return arr;
}

int rand_num(int min_num, int max_num) {
    return rand() % (max_num - min_num + 1) + min_num;
}

vector<int> rand_array(int array_empty)
{
    vector<int> temp;
    for (int i = 0; i < array_empty; i++)
    {
        temp.push_back(rand_num(1, 200));
    }
    return temp;
}


int main()
{
    int array_num;
    cin >> array_num;

    vector<int> array = rand_array(array_num);

    int max_ans = array[0], min_ans = array[0];

    for (int i = 0; i < array_num; i++) {
        if (array[i] > max_ans) { max_ans = array[i]; }
        if (array[i] < min_ans) { min_ans = array[i]; }
    }

    int max_min = max_ans - min_ans;

    vector<int> sort_array = bucket_sort(array, array_num, max_min);

    for (int i = 0; i < array_num; i++) {
        cout << sort_array[i] << '\t';
    }
    return 0;
}

为什么这段代码总会出现越界问题，如何优化？

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

在上述代码中，bucket_sort 函数试图对数组进行排序，并将其结果保存回原数组 arr。然而，当尝试将数组中的元素插入到已排序的桶内时，可能会导致越界错误。

为了解决这个问题，我们需要修改函数以确保正确处理每个桶的最大容量。这里是一个改进后的版本：

// ... 原始代码省略

void bucket_sort(vector<int>& arr, int size, int count)
{
    // ... 原始代码省略

    // 确保每个桶的容量不超过最大值
    int max_bucket_capacity = count / size + 1;
    for (int i = 0; i < size; ++i) {
        bucket[arr[i] / 10].resize(max_bucket_capacity); // 重置每个桶的大小
    }

    // ... 剩余部分保持不变
}

在这个改进后的版本中，我们首先计算每个桶的最大容量（即桶的数量除以10），然后检查数组中的每个元素是否小于这个最大容量。如果是，则我们将它添加到相应的桶中。这样可以避免因为元素超出桶的最大容量而导致的越界错误。

此外，我还建议你在整个程序中增加一些输入验证，例如检查数组长度、最小值和最大值等，以确保数据的有效性。这有助于提高程序的健壮性和可维护性。