【基本思想】

桶排序，是非比较排序中最简单一种排序方法，适用于待排序数据值域较大但分布比较均匀的情况

其基本思想是：假设待排序记录的值都在 $0$ 到 $m-1$ 之间，那么就设置 $m$ 个桶，将值为 $i$ 的记录分配到第 $i$ 个桶中，然后再将各个桶中的数据依次收集起来

【实例】

以数列 $\{3,5,3,1,5,6,3,8\}$ 为例，使用桶排序进行排序的示意图如下

【性能分析】

桶排序适用于顺序存储、链式存储结构，由于相同元素存入同一个桶，因此其是一种不稳定排序算法

对于 $n$ 个数据，其数据范围为 $(0,m-1)$，那么显然需要 $m$ 个存储空间来作为桶，因此其空间复杂度与数据范围有关，即：

$O(m)$

在最好的情况下，每个桶中只有一个数据，那么最好时间复杂度为：

$O(n)$

假设 $C$ 为桶内排序所花费的时间，那么平均时间复杂度为：

$O(n+C)$

【实现】

int bucket[m]; //m-1为数据的最大值
void bucketSort(int a[], int n) {
    for (int i = 0; i < n; i++) //将数组a存入桶中
        bucket[a[i]]++;
    
    int cnt = 0;
    for (int i = 0; i < m; i++) {
        if (bucket[i] != 0) { //桶不为空时
            a[cnt++] = i;     //收集数据
            bucket[i]--;      //桶中数据个数-1
        }
    }
}