数据结构——排序算法——桶排序

桶排序的思想是：
1.将区间划分为 n 个相同大小的子区间，每个子区间称为一个桶
2.遍历数组，将每个数字装入桶中
3.对每个桶内的数字单独排序，这里需要采用其他排序算法，如插入、归并、快排等
4.最后按照顺序将所有桶内的数字合并起来

桶排序在实际工作中的应用较少，不仅因为它需要借助于其他排序算法，还因为桶排序算法基于一个假设:所有输入数据都服从均匀分布，也就是说输入数据应该尽可能地均匀分布在每个桶中。只有这个假设成立时，桶排序运行效率才比较高。

在最差的情况下，所有数据都会被装入同一个桶中，此时桶排序算法只会徒增一轮遍历。

使用桶排序算法时，我们需要考虑两个因素
1.设置多少个桶比较合适
2.桶采用哪种数据结构

这两个因素会直接影响到桶排序的内存和效率
1.桶的数量：桶的数量过少，会导致单个桶内的数字过多，桶排序的时间复杂度就会在很大程度上受桶内排序算法的影响。桶的数量过多，占用的内存就会较大，并且会出现较多的空桶，影响遍历桶的效率。具体设置多少个桶需要根据实际情况决定。

2.桶的数据结构: 如果将桶的数据结构设置为数组，那么每个桶的长度必须设置为待排序数组的长度，因为我们需要做好最坏的打算，即所有的数字都被装入了同一个桶中，所以这种方案的空间复杂度会很高。那么是不是将桶的数据结构设置为链表就更好呢?使用链表有一个好处，即所有桶的总长度刚好等于待排序数组的长度，不会造成内存浪费。但使用链表也会有一些问题，我们待会一一分析。

// 桶排序函数
void bucketSort(std::vector<int>& arr) {
    int max = *std::max_element(arr.begin(), arr.end()); // 找到数组中的最大值
    int min = *std::min_element(arr.begin(), arr.end()); // 找到数组中的最小值
    int range = max - min + 1; // 确定桶的范围

    // 创建链表桶
    std::vector<std::list<int>> buckets(range);

    // 将元素分布到桶中
    for (int num : arr) {
        buckets[num - min].push_back(num);
    }

    // 对每个桶中的元素进行排序（使用数组排序）
    for (std::list<int>& bucket : buckets) {
        if (!bucket.empty()) {
            std::vector<int> temp(bucket.begin(), bucket.end()); // 将链表元素复制到临时数组
            std::sort(temp.begin(), temp.end()); // 对临时数组进行排序
            std::copy(temp.begin(), temp.end(), bucket.begin()); // 将排序后的结果复制回链表
        }
    }

    // 合并排序后的桶内容以获得最终结果
    int index = 0;
    for (const std::list<int>& bucket : buckets) {
        for (int num : bucket) {
            arr[index++] = num;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31