什么是桶排序法？其实说白了就是把需要排列的元素分到不同的桶中，然后我们对这些桶里的元素进行排序的一种方式，然后我们在根据桶的顺序进行元素的合并。（不过前提是要确定桶的数量以及大小）
按照稍微正式的说法是：
桶排序法是一种基于计数的排序算法。它的基本思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是排好序的序列。
具体实现时，首先确定桶的个数和每个桶所能容纳数据的范围，然后遍历待排序数据，将每个数据放入对应的桶中。接着对每个桶里的数据进行排序，可以使用其它排序算法，比如插入排序、快速排序等。最后依次取出每个桶里的有序数据，组成排序好的序列。
桶排序法的时间复杂度为O(n)，但是其空间复杂度较高，需要额外的桶来存储数据。同时，桶的个数和桶的大小需要根据数据的分布情况来确定，如果数据分布不均匀，容易导致某些桶内数据过多而造成空间浪费或者桶内排序时间过长。
动画演示（来源于哔哩哔哩up主-究尽数学）
确定桶的数量和范围：
创建空桶：
将元素分配到桶中：
对每个桶进行排序：
合并桶中的元素：
返回有序序列：
不过有一点一定要注意，那就是适用元素范围较小且数据分布相对均匀的情况。对于大范围的数据或分布不均匀的数据，可能不太使用。
下面用个示例来说明：
假如我们有一个待排序的整数数组：[35, 17, 25, 10, 42, 29, 50, 22]。我们可以使用桶排序对该数组进行排序。
大致的步骤如下：
创建桶：根据待排序数组的范围，创建一定数量的桶。假设范围为0-100，我们可以创建10个桶，每个桶表示一个范围区间，如桶0表示0-9，桶1表示10-19，以此类推。
分配元素到桶：遍历待排序数组，将每个元素根据其值分配到对应的桶中。例如，35分配到桶3，17分配到桶1，25分配到桶2，以此类推。
对每个桶进行排序：对每个非空的桶应用排序算法进行排序，可以选择插入排序、快速排序等。在本例中，我们使用插入排序对每个桶内的元素进行排序。
合并桶的结果：按照桶的顺序，将每个非空的桶中的元素按顺序合并到一个新的数组中，得到最终的排序结果。
最终得到的排序结果为：[10, 17, 22, 25, 29, 35, 42, 50]
从上面来看，桶排序适用性受到数据的规模、分布、内存以及计算等一些因素的影响。具体使用什么方式需要根据实际 的情况进行。
下面我们来举一个例子：
#include <stdio.h>
#include <stdlib.h>
// 定义桶的数量
#define BUCKET_COUNT 10
// 定义桶的结构
typedef struct
{
int count;
int *values;
} Bucket;
void bucketSort(int arr[], int n)
{
// 创建桶数组
Bucket buckets[BUCKET_COUNT];
// 初始化桶
for (int i = 0; i < BUCKET_COUNT; i++)
{
buckets[i].count = 0;
buckets[i].values = NULL;
}
// 将元素放入桶中
for (int i = 0; i < n; i++)
{
int bucketIndex = arr[i] / BUCKET_COUNT;
Bucket *bucket = &buckets[bucketIndex];
// 扩展桶的容量
bucket->values = realloc(bucket->values, (bucket->count + 1) * sizeof(int));
bucket->values[bucket->count] = arr[i];
bucket->count++;
}
// 对每个桶中的元素进行排序
for (int i = 0; i < BUCKET_COUNT; i++)
{
Bucket *bucket = &buckets[i];
int bucketSize = bucket->count;
// 使用简单的插入排序对桶中的元素进行排序
for (int j = 1; j < bucketSize; j++)
{
int key = bucket->values[j];
int k = j - 1;
while (k >= 0 && bucket->values[k] > key)
{
bucket->values[k + 1] = bucket->values[k];
k--;
}
bucket->values[k + 1] = key;
}
}
// 合并桶中的元素到原始数组
int index = 0;
for (int i = 0; i < BUCKET_COUNT; i++)
{
Bucket *bucket = &buckets[i];
int bucketSize = bucket->count;
for (int j = 0; j < bucketSize; j++)
{
arr[index] = bucket->values[j];
index++;
}
free(bucket->values);
}
}
int main()
{
int arr[] = {29, 25, 3, 49, 9, 37, 21, 43, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("原始数组：\n");
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
bucketSort(arr, n);
printf("排序后的数组：\n");
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
void bucketSort(std::vector<int> &arr, int bucketSize)
{
if (arr.empty())
{
return;
}
// 找到最大值和最小值
int minValue = arr[0];
int maxValue = arr[0];
for (int i = 1; i < arr.size(); i++)
{
if (arr[i] < minValue)
{
minValue = arr[i];
}
else if (arr[i] > maxValue)
{
maxValue = arr[i];
}
}
// 计算桶的数量
int bucketCount = (maxValue - minValue) / bucketSize + 1;
// 创建桶
std::vector<std::vector<int>> buckets(bucketCount);
// 将元素分配到桶中
for (int i = 0; i < arr.size(); i++)
{
int bucketIndex = (arr[i] - minValue) / bucketSize;
buckets[bucketIndex].push_back(arr[i]);
}
// 对每个桶中的元素进行排序
for (int i = 0; i < buckets.size(); i++)
{
std::sort(buckets[i].begin(), buckets[i].end());
}
// 合并桶中的元素
int index = 0;
for (int i = 0; i < buckets.size(); i++)
{
for (int j = 0; j < buckets[i].size(); j++)
{
arr[index++] = buckets[i][j];
}
}
}
int main()
{
std::vector<int> arr = {45, 12, 36, 78, 53, 21, 67};
int bucketSize = 10;
std::cout << "原始数据: ";
for (int num : arr)
{
std::cout << num << " ";
}
bucketSort(arr, bucketSize);
std::cout << "\n排列之后的数据: ";
for (int num : arr)
{
std::cout << num << " ";
}
return 0;
}
