11.8 桶排序¶
前述几种排序算法都属于“基于比较的排序算法”,它们通过比较元素间的大小来实现排序。此类排序算法在最坏情况下的时间复杂度下界为 \(\Omega(n \log n)\) 。接下来,我们将探讨几种“非比较排序算法”,它们的时间复杂度可以达到线性阶。
桶排序(bucket sort)是分治策略的一个典型应用。它通过设置一些具有大小顺序的桶,每个桶对应一个数据范围,将数据平均分配到各个桶中;然后,在每个桶内部分别执行排序;最终按照桶的顺序将所有数据合并。
11.8.1 算法流程¶
考虑一个长度为 \(n\) 的数组,其元素是范围 \([0, 1)\) 内的浮点数。桶排序的流程如图 11-13 所示。
- 初始化 \(k\) 个桶,将 \(n\) 个元素分配到 \(k\) 个桶中。
- 对每个桶分别执行排序(这里采用编程语言的内置排序函数)。
- 按照桶从小到大的顺序合并结果。
图 11-13 桶排序算法流程
图解 11-13:分成五个桶,桶内排序后依次合并
十个小数按数值范围分入五个桶,桶内分别升序排序,再按桶序连接成有序数组。
输入数组为 nums = [0.49, 0.96, 0.82, 0.09, 0.57, 0.43, 0.91, 0.75, 0.15, 0.37],全部元素均为 [0, 1) 区间内的浮点数,算法设置五个宽度为 0.2 的桶。
先将每个数放入它所属的左闭右开区间,再分别对桶内元素排序。图中中部的五个桶已完成这两项操作,并不展示刚入桶时的先后顺序。
最后按区间从小到大的桶序拼接;由于桶的数值范围互不重叠,各桶内部也已升序,拼接后即为完整有序数组。
| 索引 | 值 |
|---|---|
| 0 | 0.49 |
| 1 | 0.96 |
| 2 | 0.82 |
| 3 | 0.09 |
| 4 | 0.57 |
| 5 | 0.43 |
| 6 | 0.91 |
| 7 | 0.75 |
| 8 | 0.15 |
| 9 | 0.37 |
| 桶范围 | 桶内升序结果 |
|---|---|
| [0,0.2) | 0.09、0.15 |
| [0.2,0.4) | 0.37 |
| [0.4,0.6) | 0.43、0.49、0.57 |
| [0.6,0.8) | 0.75 |
| [0.8,1.0) | 0.82、0.91、0.96 |
拼接结果为 [0.09, 0.15, 0.37, 0.43, 0.49, 0.57, 0.75, 0.82, 0.91, 0.96]。
代码如下所示:
def bucket_sort(nums: list[float]):
"""桶排序"""
# 初始化 k = n/2 个桶,预期向每个桶分配 2 个元素
k = len(nums) // 2
buckets = [[] for _ in range(k)]
# 1. 将数组元素分配到各个桶中
for num in nums:
# 输入数据范围为 [0, 1),使用 num * k 映射到索引范围 [0, k-1]
i = int(num * k)
# 将 num 添加进桶 i
buckets[i].append(num)
# 2. 对各个桶执行排序
for bucket in buckets:
# 使用内置排序函数,也可以替换成其他排序算法
bucket.sort()
# 3. 遍历桶合并结果
i = 0
for bucket in buckets:
for num in bucket:
nums[i] = num
i += 1
/* 桶排序 */
void bucketSort(vector<float> &nums) {
// 初始化 k = n/2 个桶,预期向每个桶分配 2 个元素
int k = nums.size() / 2;
vector<vector<float>> buckets(k);
// 1. 将数组元素分配到各个桶中
for (float num : nums) {
// 输入数据范围为 [0, 1),使用 num * k 映射到索引范围 [0, k-1]
int i = num * k;
// 将 num 添加进桶 bucket_idx
buckets[i].push_back(num);
}
// 2. 对各个桶执行排序
for (vector<float> &bucket : buckets) {
// 使用内置排序函数,也可以替换成其他排序算法
sort(bucket.begin(), bucket.end());
}
// 3. 遍历桶合并结果
int i = 0;
for (vector<float> &bucket : buckets) {
for (float num : bucket) {
nums[i++] = num;
}
}
}
/* 桶排序 */
void bucketSort(float[] nums) {
// 初始化 k = n/2 个桶,预期向每个桶分配 2 个元素
int k = nums.length / 2;
List<List<Float>> buckets = new ArrayList<>();
for (int i = 0; i < k; i++) {
buckets.add(new ArrayList<>());
}
// 1. 将数组元素分配到各个桶中
for (float num : nums) {
// 输入数据范围为 [0, 1),使用 num * k 映射到索引范围 [0, k-1]
int i = (int) (num * k);
// 将 num 添加进桶 i
buckets.get(i).add(num);
}
// 2. 对各个桶执行排序
for (List<Float> bucket : buckets) {
// 使用内置排序函数,也可以替换成其他排序算法
Collections.sort(bucket);
}
// 3. 遍历桶合并结果
int i = 0;
for (List<Float> bucket : buckets) {
for (float num : bucket) {
nums[i++] = num;
}
}
}
/* 桶排序 */
void BucketSort(float[] nums) {
// 初始化 k = n/2 个桶,预期向每个桶分配 2 个元素
int k = nums.Length / 2;
List<List<float>> buckets = [];
for (int i = 0; i < k; i++) {
buckets.Add([]);
}
// 1. 将数组元素分配到各个桶中
foreach (float num in nums) {
// 输入数据范围为 [0, 1),使用 num * k 映射到索引范围 [0, k-1]
int i = (int)(num * k);
// 将 num 添加进桶 i
buckets[i].Add(num);
}
// 2. 对各个桶执行排序
foreach (List<float> bucket in buckets) {
// 使用内置排序函数,也可以替换成其他排序算法
bucket.Sort();
}
// 3. 遍历桶合并结果
int j = 0;
foreach (List<float> bucket in buckets) {
foreach (float num in bucket) {
nums[j++] = num;
}
}
}
/* 桶排序 */
func bucketSort(nums []float64) {
// 初始化 k = n/2 个桶,预期向每个桶分配 2 个元素
k := len(nums) / 2
buckets := make([][]float64, k)
for i := 0; i < k; i++ {
buckets[i] = make([]float64, 0)
}
// 1. 将数组元素分配到各个桶中
for _, num := range nums {
// 输入数据范围为 [0, 1),使用 num * k 映射到索引范围 [0, k-1]
i := int(num * float64(k))
// 将 num 添加进桶 i
buckets[i] = append(buckets[i], num)
}
// 2. 对各个桶执行排序
for i := 0; i < k; i++ {
// 使用内置切片排序函数,也可以替换成其他排序算法
sort.Float64s(buckets[i])
}
// 3. 遍历桶合并结果
i := 0
for _, bucket := range buckets {
for _, num := range bucket {
nums[i] = num
i++
}
}
}
/* 桶排序 */
func bucketSort(nums: inout [Double]) {
// 初始化 k = n/2 个桶,预期向每个桶分配 2 个元素
let k = nums.count / 2
var buckets = (0 ..< k).map { _ in [Double]() }
// 1. 将数组元素分配到各个桶中
for num in nums {
// 输入数据范围为 [0, 1),使用 num * k 映射到索引范围 [0, k-1]
let i = Int(num * Double(k))
// 将 num 添加进桶 i
buckets[i].append(num)
}
// 2. 对各个桶执行排序
for i in buckets.indices {
// 使用内置排序函数,也可以替换成其他排序算法
buckets[i].sort()
}
// 3. 遍历桶合并结果
var i = nums.startIndex
for bucket in buckets {
for num in bucket {
nums[i] = num
i += 1
}
}
}
/* 桶排序 */
function bucketSort(nums) {
// 初始化 k = n/2 个桶,预期向每个桶分配 2 个元素
const k = nums.length / 2;
const buckets = [];
for (let i = 0; i < k; i++) {
buckets.push([]);
}
// 1. 将数组元素分配到各个桶中
for (const num of nums) {
// 输入数据范围为 [0, 1),使用 num * k 映射到索引范围 [0, k-1]
const i = Math.floor(num * k);
// 将 num 添加进桶 i
buckets[i].push(num);
}
// 2. 对各个桶执行排序
for (const bucket of buckets) {
// 使用内置排序函数,也可以替换成其他排序算法
bucket.sort((a, b) => a - b);
}
// 3. 遍历桶合并结果
let i = 0;
for (const bucket of buckets) {
for (const num of bucket) {
nums[i++] = num;
}
}
}
/* 桶排序 */
function bucketSort(nums: number[]): void {
// 初始化 k = n/2 个桶,预期向每个桶分配 2 个元素
const k = nums.length / 2;
const buckets: number[][] = [];
for (let i = 0; i < k; i++) {
buckets.push([]);
}
// 1. 将数组元素分配到各个桶中
for (const num of nums) {
// 输入数据范围为 [0, 1),使用 num * k 映射到索引范围 [0, k-1]
const i = Math.floor(num * k);
// 将 num 添加进桶 i
buckets[i].push(num);
}
// 2. 对各个桶执行排序
for (const bucket of buckets) {
// 使用内置排序函数,也可以替换成其他排序算法
bucket.sort((a, b) => a - b);
}
// 3. 遍历桶合并结果
let i = 0;
for (const bucket of buckets) {
for (const num of bucket) {
nums[i++] = num;
}
}
}
/* 桶排序 */
void bucketSort(List<double> nums) {
// 初始化 k = n/2 个桶,预期向每个桶分配 2 个元素
int k = nums.length ~/ 2;
List<List<double>> buckets = List.generate(k, (index) => []);
// 1. 将数组元素分配到各个桶中
for (double _num in nums) {
// 输入数据范围为 [0, 1),使用 _num * k 映射到索引范围 [0, k-1]
int i = (_num * k).toInt();
// 将 _num 添加进桶 bucket_idx
buckets[i].add(_num);
}
// 2. 对各个桶执行排序
for (List<double> bucket in buckets) {
bucket.sort();
}
// 3. 遍历桶合并结果
int i = 0;
for (List<double> bucket in buckets) {
for (double _num in bucket) {
nums[i++] = _num;
}
}
}
/* 桶排序 */
fn bucket_sort(nums: &mut [f64]) {
// 初始化 k = n/2 个桶,预期向每个桶分配 2 个元素
let k = nums.len() / 2;
let mut buckets = vec![vec![]; k];
// 1. 将数组元素分配到各个桶中
for &num in nums.iter() {
// 输入数据范围为 [0, 1),使用 num * k 映射到索引范围 [0, k-1]
let i = (num * k as f64) as usize;
// 将 num 添加进桶 i
buckets[i].push(num);
}
// 2. 对各个桶执行排序
for bucket in &mut buckets {
// 使用内置排序函数,也可以替换成其他排序算法
bucket.sort_by(|a, b| a.partial_cmp(b).unwrap());
}
// 3. 遍历桶合并结果
let mut i = 0;
for bucket in buckets.iter() {
for &num in bucket.iter() {
nums[i] = num;
i += 1;
}
}
}
/* 桶排序 */
void bucketSort(float nums[], int n) {
int k = n / 2; // 初始化 k = n/2 个桶
int *sizes = malloc(k * sizeof(int)); // 记录每个桶的大小
float **buckets = malloc(k * sizeof(float *)); // 动态数组的数组(桶)
// 为每个桶预分配足够的空间
for (int i = 0; i < k; ++i) {
buckets[i] = (float *)malloc(n * sizeof(float));
sizes[i] = 0;
}
// 1. 将数组元素分配到各个桶中
for (int i = 0; i < n; ++i) {
int idx = (int)(nums[i] * k);
buckets[idx][sizes[idx]++] = nums[i];
}
// 2. 对各个桶执行排序
for (int i = 0; i < k; ++i) {
qsort(buckets[i], sizes[i], sizeof(float), compare);
}
// 3. 合并排序后的桶
int idx = 0;
for (int i = 0; i < k; ++i) {
for (int j = 0; j < sizes[i]; ++j) {
nums[idx++] = buckets[i][j];
}
// 释放内存
free(buckets[i]);
}
}
/* 桶排序 */
fun bucketSort(nums: FloatArray) {
// 初始化 k = n/2 个桶,预期向每个桶分配 2 个元素
val k = nums.size / 2
val buckets = mutableListOf<MutableList<Float>>()
for (i in 0..<k) {
buckets.add(mutableListOf())
}
// 1. 将数组元素分配到各个桶中
for (num in nums) {
// 输入数据范围为 [0, 1),使用 num * k 映射到索引范围 [0, k-1]
val i = (num * k).toInt()
// 将 num 添加进桶 i
buckets[i].add(num)
}
// 2. 对各个桶执行排序
for (bucket in buckets) {
// 使用内置排序函数,也可以替换成其他排序算法
bucket.sort()
}
// 3. 遍历桶合并结果
var i = 0
for (bucket in buckets) {
for (num in bucket) {
nums[i++] = num
}
}
}
### 桶排序 ###
def bucket_sort(nums)
# 初始化 k = n/2 个桶,预期向每个桶分配 2 个元素
k = nums.length / 2
buckets = Array.new(k) { [] }
# 1. 将数组元素分配到各个桶中
nums.each do |num|
# 输入数据范围为 [0, 1),使用 num * k 映射到索引范围 [0, k-1]
i = (num * k).to_i
# 将 num 添加进桶 i
buckets[i] << num
end
# 2. 对各个桶执行排序
buckets.each do |bucket|
# 使用内置排序函数,也可以替换成其他排序算法
bucket.sort!
end
# 3. 遍历桶合并结果
i = 0
buckets.each do |bucket|
bucket.each do |num|
nums[i] = num
i += 1
end
end
end
可视化运行
11.8.2 算法特性¶
桶排序适用于处理体量很大的数据。例如,输入数据包含 100 万个元素,由于空间限制,系统内存无法一次性加载所有数据。此时,可以将数据分成 1000 个桶,然后分别对每个桶进行排序,最后将结果合并。
- 时间复杂度为 \(O(n + k)\) :假设元素在各个桶内平均分布,那么每个桶内的元素数量为 \(\frac{n}{k}\) 。假设排序单个桶使用 \(O(\frac{n}{k} \log\frac{n}{k})\) 时间,则排序所有桶使用 \(O(n \log\frac{n}{k})\) 时间。当桶数量 \(k\) 比较大时,时间复杂度则趋向于 \(O(n)\) 。合并结果时需要遍历所有桶和元素,花费 \(O(n + k)\) 时间。在最差情况下,所有数据被分配到一个桶中,且排序该桶使用 \(O(n^2)\) 时间。
- 空间复杂度为 \(O(n + k)\)、非原地排序:需要借助 \(k\) 个桶和总共 \(n\) 个元素的额外空间。
- 桶排序是否稳定取决于排序桶内元素的算法是否稳定。
11.8.3 如何实现平均分配¶
桶排序的时间复杂度理论上可以达到 \(O(n)\) ,关键在于将元素均匀分配到各个桶中,因为实际数据往往不是均匀分布的。例如,我们想要将淘宝上的所有商品按价格范围平均分配到 10 个桶中,但商品价格分布不均,低于 100 元的非常多,高于 1000 元的非常少。若将价格区间平均划分为 10 个,各个桶中的商品数量差距会非常大。
为实现平均分配,我们可以先设定一条大致的分界线,将数据粗略地分到 3 个桶中。分配完毕后,再将商品较多的桶继续划分为 3 个桶,直至所有桶中的元素数量大致相等。
如图 11-14 所示,这种方法本质上是创建一棵递归树,目标是让叶节点的值尽可能平均。当然,不一定要每轮将数据划分为 3 个桶,具体划分方式可根据数据特点灵活选择。
图 11-14 递归划分桶
图解 11-14:递归拆分数据过多的价格桶
先将商品粗分为三个价格桶,再递归拆分占比 65% 与 35% 的密集桶,得到七个较均衡的叶桶。
每个桶标注的“数据占比”均指占全部商品数据的百分比,而非占其父桶的比例。图中给出价格范围标签和单桶占比,没有商品总数、货币单位或完整的端点分配规则。
顶部“商品数据”的分支箭头表示逐层细分;没有继续拆分的桶保留为叶节点。第一层粗分将商品数据划分为三个价格桶:<100 占 65%,100–500 占 20%,>500 占 15%。由于 <100 桶集中了 65% 的数据,继续将该桶向下细分为三个子桶。
第二层将 <100 桶拆分为:<10 占 18%,10–50 占 35%,50–100 占 12%,由图中占比相加可得 18% + 35% + 12% = 65%。其中 10–50 桶占比仍明显偏高(35%),因此再向下一层细分为 10–20 占 13%、20–35 占 12%、35–50 占 10%,由占比相加可得 13% + 12% + 10% = 35%。
画面右侧“数据划分结果”汇总了递归树的七个叶节点桶(详见附表),各叶桶占比分布在 10% 至 20% 之间,显著比初始的 65%、20%、15% 更均衡。中间层的 65% 和 35% 属于已被拆开的父桶汇总,不再计入最终结果桶。
| 图示价格区间 | 全部数据占比 |
|---|---|
| <10 | 18% |
| 10–20 | 13% |
| 20–35 | 12% |
| 35–50 | 10% |
| 50–100 | 12% |
| 100–500 | 20% |
| >500 | 15% |
由七个叶桶的占比相加可得总和 100%;叶桶各占 10% 至 20%,拆分后的数据量更均衡。编码时须将图示范围补成完整的端点分配规则。
如果我们提前知道商品价格的概率分布,则可以根据数据概率分布设置每个桶的价格分界线。值得注意的是,数据分布并不一定需要特意统计,也可以根据数据特点采用某种概率模型进行近似。
如图 11-15 所示,我们假设商品价格服从正态分布,这样就可以合理地设定价格区间,从而将商品平均分配到各个桶中。
图 11-15 根据概率分布划分桶
图解 11-15:按价格分布划分桶
根据商品价格的概率分布设置分界点,使落入各桶的数据概率尽量接近,避免数据集中挤入少数桶。
图中横轴表示商品价格,从左到右依次标出 0、3、10、25、80、200、+∞;纵轴表示概率密度,刻度为 0.0 至 0.4。灰色钟形曲线在价格 25 附近达到峰值,仅作分布形态示意,图中未给出分布函数参数或各桶的精确概率数值。
需要特别注意横轴是非线性示意坐标:相邻刻度之间的价格差(如 0 到 3 相差 3,80 到 200 相差 120)与图上的水平像素宽度不成比例。因此,不能根据图上各桶的视觉宽度判断真实价格跨度,也不能直接量取画面中的曲线下面积来推算精确入桶概率。
曲线下方的六个大括号分别对应下表六桶,最右桶没有有限上界。分桶目标是根据真实分布的区间概率,使各桶的期望数据量大致接近;图中未给精确概率,不能据此认定六桶严格等概率。
| 桶序号 | 原图价格范围 |
|---|---|
| 1 | <3 |
| 2 | 3~10 |
| 3 | 10~25 |
| 4 | 25~80 |
| 5 | 80~200 |
| 6 | >200 |
标签 <3 排除价格 3,>200 排除价格 200;中间的“3~10”等标签没有明确端点开闭。若六桶完整覆盖价格范围,则 3 应进入第二桶、200 应进入第五桶,这是按覆盖要求作的推断。图未写出完整的端点分配规则,10、25、80 等相邻桶分界仍须在实现时明确。