title: 桶排序
date: 2024-7-25 18:58:19 +0800
categories:
- 排序算法
tags: - 排序
- 算法
- 桶排序
description: 桶排序(bucket sort)是分治策略的一个典型应用。它通过设置一些具有大小顺序的桶,每个桶对应一个数据范围,将数据平均分配到各个桶中;然后,在每个桶内部分别执行排序;最终按照桶的顺序将所有数据合并。
math: true
桶排序
桶排序(Bucket Sort)是一种基于分配的排序算法。它将元素分散到不同的桶中,然后对每个桶分别进行排序,最后将桶中的元素合并起来。
桶排序的原理
桶排序适用于均匀分布在一定范围内的数值。其主要思想是:
- 创建若干桶:将要排序的数据分到若干个桶中。
- 对每个桶内的数据进行排序:桶内的排序可以使用任意排序算法。
- 合并所有桶中的数据:将排好序的桶中的数据合并,得到最终的有序数据。
桶排序的步骤
- 创建桶:根据数据范围和桶的数量,创建若干个桶。
- 分配数据:将数据分配到对应的桶中。
- 桶内排序:对每个桶中的数据进行排序。
- 合并数据:将所有桶中的数据按顺序合并,得到排序后的结果。
图示
示例
以下是一个桶排序的示例,假设我们有一个浮点数数组:[0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51]。
第一步:创建桶
假设我们创建10个桶,每个桶对应范围是[0, 0.1),[0.1, 0.2),[0.2, 0.3)等。
第二步:分配数据
将每个数据分配到对应的桶中:
- 0.42 -> 桶4
- 0.32 -> 桶3
- 0.23 -> 桶2
- 0.52 -> 桶5
- 0.25 -> 桶2
- 0.47 -> 桶4
- 0.51 -> 桶5
第三步:桶内排序
对每个桶中的数据进行排序:
- 桶2: [0.23, 0.25]
- 桶3: [0.32]
- 桶4: [0.42, 0.47]
- 桶5: [0.51, 0.52]
第四步:合并数据
将所有桶中的数据合并:[0.23, 0.25, 0.32, 0.42, 0.47, 0.51, 0.52]
复杂度分析
桶排序适用于处理体量很大的数据。例如,输入数据包含 100 万个元素,由于空间限制,系统内存无法一次性加载所有数据。此时,可以将数据分成 1000 个桶,然后分别对每个桶进行排序,最后将结果合并。
- 时间复杂度为 O ( n + k ) O(n + k) O(n+k) :假设元素在各个桶内平均分布,那么每个桶内的元素数量为 n k \frac{n}{k} kn 。假设排序单个桶使用 O ( n k log n k ) O(\frac{n}{k} \log\frac{n}{k}) O(knlogkn) 时间,则排序所有桶使用 O ( n log n k ) O(n \log\frac{n}{k}) O(nlogkn) 时间。当桶数量 k k k 比较大时,时间复杂度则趋向于 O ( n ) O(n) O(n) 。合并结果时需要遍历所有桶和元素,花费 O ( n + k ) O(n + k) O(n+k) 时间。
- 自适应排序:在最差情况下,所有数据被分配到一个桶中,且排序该桶使用 O ( n 2 ) O(n^2) O(n2) 时间。
- 空间复杂度为 O ( n + k ) O(n + k) O(n+k)、非原地排序:需要借助 k k k 个桶和总共 n n n 个元素的额外空间。
- 桶排序是否稳定取决于排序桶内元素的算法是否稳定。
时间复杂度
- 最佳情况: O ( n ) O(n) O(n)。
- 最坏情况: O ( n 2 ) O(n^2) O(n2)。
- 平均情况: O ( n + k ) O(n+k) O(n+k)。
空间复杂度
- 空间复杂度: O ( n ⋅ k ) O(n \cdot k) O(n⋅k)
如何实现平均分配
桶排序的时间复杂度理论上可以达到 O ( n ) O(n) O(n) ,关键在于将元素均匀分配到各个桶中,因为实际数据往往不是均匀分布的。若将区间平均划分为 10 个,各个桶中的数据的数量差距会非常大。
为实现平均分配,我们可以先设定一条大致的分界线,将数据粗略地分到 3 个桶中。分配完毕后,再将数据较多的桶继续划分为 3 个桶,直至所有桶中的元素数量大致相等。
这种方法本质上是创建一棵递归树,目标是让叶节点的值尽可能平均。当然,不一定要每轮将数据划分为 3 个桶,具体划分方式可根据数据特点灵活选择。
如果我们提前知道数据的概率分布,则可以根据数据概率分布设置每个桶的价格分界线。值得注意的是,数据分布并不一定需要特意统计,也可以根据数据特点采用某种概率模型进行近似。
Java代码实现
/* 桶排序 */
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 添加进桶 ibuckets.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;}}
}