桶排序算法（Java, Python， C/C++ Code 例如）
陈莎拉
什么是桶排序？
桶排序（也称分桶排序）是一种基于比较的分布排序方法，它接受一个未排序的数组作为输入，并生成一个已排序的数组作为输出。该方法将元素分配到多个桶中，并使用其他排序算法（例如插入排序）分别对每个桶进行排序。然后，将所有桶合并在一起，形成最终的已排序数组。
当元素满足以下条件时，通常使用桶排序：
- 浮点值
- 在已知范围内均匀分布
桶排序的时间复杂度取决于使用的桶的数量和输入分布的均匀性。而其他排序算法，例如…… 壳排序、归并排序、堆排序和 快速排序 桶排序算法在最佳情况下可以达到 O(n*logn) 的时间复杂度，在有利条件下可以达到线性时间复杂度 O(n)。
桶排序采用分散-聚集策略。元素被分散到相应的桶中，在每个桶内进行排序，最后将所有桶内的元素聚集起来，形成一个排序后的数组。这种分散-聚集策略将在下一节中讨论。
分散聚集法
大规模、复杂的问题有时难以直接解决。分散-聚集法通过将整个数据集划分为多个簇来解决此类问题。每个簇分别进行处理，然后将结果重新组合以得出最终答案。
以下是桶排序算法实现分散聚集方法的方式：
桶排序的工作原理
桶排序的基本工作原理如下：
- 创建一组空桶。根据所选策略，桶的数量可能会有所不同。
- 将输入数组中的每个元素放入其对应的桶中。
- 每个桶都使用辅助排序算法单独排序。
- 将排序后的桶连接起来，生成一个输出数组。
昵称 Code
Start Create N empty buckets For each array element: Calculate bucket index Put that element into the corresponding bucket For each bucket: Sort elements within each bucket Merge all the elements from each bucket Output the sorted array End
方法 1：浮点数的桶排序算法 Numbers
桶排序算法适用于 [0.0, 1.0] 范围内的浮点数：
步骤1） 创建十 (10) 个空桶。第一个桶存放 [0.0, 0.1) 范围内的数字。第二个桶存放 [0.1, 0.2) 范围内的数字，依此类推。
步骤2） 对于每个数组元素：
- a. 使用以下公式计算桶索引：
bucket_index = 桶数 * 数组元素 - b. 将元素插入 bucket[bucket_index]
步骤3） 使用插入排序对每个桶单独进行排序。
步骤4） 将所有桶连接成一个已排序的数组。
让我们来看一个桶排序的例子。在这个例子中，我们将对以下数组进行排序：
步骤1） 首先，我们创建 10 个空桶。第一个桶里装的是 [0.0, 0.1) 范围内的数字。第二个桶里装的是 [0.1, 0.2) 范围内的数字，依此类推。
步骤2） 对于数组中的每个元素，计算桶索引并将该元素放入相应的桶中。
桶索引的计算公式为：
bucket_index = 桶数 * 数组元素
桶索引计算：
一）0.78
bucket_index = 桶数 * 数组元素
=10*0.78
= 7.8
因此，元素 0.78 存储在 bucket[floor(7.8)] 或 bucket[7] 中。
二）0.17处
bucket_index = 桶数 * 数组元素
=10*0.17
= 1.7
数组元素 0.17 存储在 bucket[floor(1.7)] 或 bucket[1] 中。
C）0.39
bucket_index = 桶数 * 数组元素
=10*0.39
= 3.9
0.39 存储在 bucket[floor(3.9)] 或 bucket[3] 中。
遍历完所有数组元素后，桶的形状如下所示：
步骤3） 然后对每个桶进行插入排序。排序操作后，输出结果为：
步骤4） 最后一步，将所有桶连接成一个数组。该数组就是输入数据的排序结果。
每个桶的元素都连接到输出数组中。例如，第二个桶的元素连接如下：
最后一个桶元素的连接结果如下所示：
连接后得到的数组就是所需的排序数组。
C/ 中的桶排序程序C++
输入：
//Bucket Sort Program in C/C++ //For values without integer parts #include <bits/stdc++.h> #define BUCKET_SIZE 10 using namespace std; void bucketSort(float input[], int array_size) { vector <float>bucket[BUCKET_SIZE]; for (int i = 0; i < array_size; i++) { int index = BUCKET_SIZE*input[i]; bucket[index].push_back(input[i]); } for (int i = 0; i < BUCKET_SIZE; i++) sort(bucket[i].begin(), bucket[i].end()); int out_index = 0; for (int i = 0; i < BUCKET_SIZE; i++) for (int j = 0; j < bucket[i].size(); j++) input[out_index++] = bucket[i][j]; } int main() { float input[]={0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.69}; int array_size = sizeof(input)/sizeof(input[0]); bucketSort(input, array_size); cout <<"Sorted Output: "; for (int i = 0; i< array_size; i++) cout<<input[i]<<" "; return 0; }
输出：
Sorted Output: 0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94
桶排序程序 Python
输入：
# Bucket Sort Program in Python # For values without integer parts def bucketSort(input): output = [] bucket_size = 10 for bucket in range(bucket_size): output.append([]) for element in input: index = int(bucket_size * element) output[index].append(element) for bucket in range(bucket_size): output[bucket] = sorted(output[bucket]) out_index = 0 for bucket in range(bucket_size): for element in range(len(output[bucket])): input[out_index] = output[bucket][element] out_index += 1 return input input = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.69] print("Sorted Output:") print(bucketSort(input))
输出：
Sorted Output: [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.69, 0.72, 0.78, 0.94]
桶排序 Java
输入：
import java.util.ArrayList; import java.util.Collections; import java.util.List; public class BucketSort { private static final int BUCKET_SIZE = 10; public static void bucketSort(float[] input, int arraySize) { List<Float>[] bucket = new ArrayList[BUCKET_SIZE]; for (int i = 0; i < arraySize; i++) { int index = (int)(BUCKET_SIZE * input[i]); if (bucket[index] == null) { bucket[index] = new ArrayList<>(); } bucket[index].add(input[i]); } for (int i = 0; i < BUCKET_SIZE; i++) { if (bucket[i] != null) { Collections.sort(bucket[i]); } } int outIndex = 0; for (int i = 0; i < BUCKET_SIZE; i++) { if (bucket[i] != null) { for (float value: bucket[i]) { input[outIndex++] = value; } } } } public static void main(String[] args) { float[] input = {0.78f,0.17f,0.39f,0.26f,0.72f,0.94f,0.21f,0.12f,0.23f,0.69f}; int arraySize = input.length; bucketSort(input, arraySize); System.out.println("Sorted Output:"); for (int i = 0; i < arraySize; i++) { System.out.print(input[i]+" "); } } }
输出：
Sorted Output: 0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94
方法 2：整数元素的桶排序算法
对于包含超出 [0.0, 1.0] 范围的数字的输入，桶排序算法与之前的算法略有不同。 算法本案所需步骤如下：
步骤1） 找出数组中的最大值和最小值。
步骤2） 选择桶的数量 n，并将它们初始化为空。
步骤3） 使用以下公式计算每个桶的范围或跨度：
span = (maximum - minimum) / n
步骤4） 对于每个数组元素：
- 1. 计算桶索引：
bucket_index = (element - minimum) / span - 2. 将元素插入 bucket[bucket_index]
步骤5） 使用插入排序对每个桶进行排序。
步骤6） 将所有存储桶连接成一个数组。
让我们来看一个桶排序算法的例子。在这个例子中，我们将对以下数组进行排序：
步骤1） 第一步，我们找出给定数组中的最大值和最小值。在本例中，最大值是 24，最小值是 1。
步骤2） 接下来，我们选择空桶的数量 n。在本例中，我们使用 5 个桶，并将它们初始化为空。
步骤3） 每个桶的跨度使用以下公式计算：
span = (maximum - minimum) / n = (24 - 1) / 5 = 4
因此，第一个桶包含 [0, 5) 范围内的数字，第二个桶包含 [5, 10) 范围内的数字，依此类推。
步骤4） 对于数组中的每个元素，计算其桶索引并将该元素放入相应的桶中。桶索引的计算公式为：
bucket_index = (element - minimum) / span
桶索引计算：
一）11
bucket_index = (元素 – 最小值) / span
=（11-1）/ 4
= 2
因此，元素 11 存储在桶[2]中。
二）9处
bucket_index = (元素 – 最小值) / span
=（9-1）/ 4
= 2
注意： 由于 9 是 bucket[1] 的边界元素，因此它被附加到 bucket[1]，而不是与前一个元素放在同一个 bucket 中。
对每个元素执行操作后，桶如下所示：
步骤5） 现在，每个桶都使用插入排序进行排序。排序后的桶如下：
步骤6） 最后一步，将所有桶连接成一个数组。 排列 是输入的排序结果。
C/ 中的桶排序程序C++
输入：
#include<bits/stdc++.h> using namespace std; void bucketSort(vector < double > & input, int No_Of_Buckets) { double max_value = * max_element(input.begin(), input.end()); double min_value = * min_element(input.begin(), input.end()); double span = (max_value - min_value) / No_Of_Buckets; vector<vector <double>> output; for (int i = 0; i < No_Of_Buckets; i++) output.push_back(vector <double>()); for (int i = 0; i < input.size(); i++) { double difference = (input[i] - min_value) / span - int((input[i] - min_value) / span); if (difference == 0 && input[i] != min_value) output[int((input[i] - min_value) / span) - 1].push_back(input[i]); else output[int((input[i] - min_value) / span)].push_back(input[i]); } for (int i = 0; i < output.size(); i++) { if (!output[i].empty()) sort(output[i].begin(), output[i].end()); } int index = 0; for (vector <double> & bucket: output) { if (!bucket.empty()) { for (double i: bucket) { input[index] = i; index++; } } } } int main() { vector <double> input ={11,9,21,8,17,19,13,1,24,12}; int No_Of_Buckets = 5; bucketSort(input, No_Of_Buckets); cout<<"Sorted Output:"; for (int i=0; i < input.size(); i++) cout <<input[i]<<" "; return 0; }
输出：
Sorted Output:1 8 9 11 12 13 17 19 21 24
桶排序程序 Python
输入：
def bucketSort(input, No_Of_Buckets): max_element = max(input) min_element = min(input) span = (max_element - min_element) / No_Of_Buckets output = [] for bucket in range(No_Of_Buckets): output.append([]) for element in range(len(input)): diff = (input[element] - min_element) / span - int( (input[element] - min_element) / span ) if diff == 0 and input[element] != min_element: output[int((input[element] - min_element) / span) - 1].append( input[element] ) else: output[int((input[element] - min_element) / span)].append(input[element]) for bucket in range(len(output)): if len(output[bucket]) != 0: output[bucket].sort() index = 0 for bucket in output: if bucket: for element in bucket: input[index] = element index = index + 1 input = [11, 9, 21, 8, 17, 19, 13, 1, 24, 12] No_Of_Buckets = 5 bucketSort(input, No_Of_Buckets) print("Sorted Output: ", input)
输出：
Sorted Output: [1, 8, 9, 11, 12, 13, 17, 19, 21, 24]
桶排序 Java
输入：
import java.util.ArrayList; import java.util.Collections; import java.util.List; public class BucketSort { public static void bucketSort(List < Double > input, int No_Of_Buckets) { double max_value = Collections.max(input); double min_value = Collections.min(input); double span =(max_value - min_value) / No_Of_Buckets; List<List<Double>> output = new ArrayList<>(); for (int i = 0; i < No_Of_Buckets; i++) { output.add(new ArrayList<>()); } for (Double value: input) { double difference = (value - min_value) / span - ((value - min_value) / span); if (difference == 0 && value != min_value) { output.get((int)((value - min_value) / span) - 1).add(value); } else { output.get((int)((value - min_value) / span)).add(value); } } for (List <Double> bucket: output) { if (!bucket.isEmpty()) { Collections.sort(bucket); } } int index = 0; for (List <Double> bucket: output) { if (!bucket.isEmpty()) { for (Double value: bucket) { input.set(index,value); index++; } } } } public static void main(String[] args) { List <Double> input = new ArrayList<>(); input.add(11.0); input.add(9.0); input.add(21.0); input.add(8.0); input.add(17.0); input.add(19.0); input.add(13.0); input.add(1.0); input.add(24.0); input.add(12.0); int No_Of_Buckets = 5; bucketSort(input, No_Of_Buckets); System.out.println("Sorted Output:"); for (Double value: input) { System.out.print(value + " "); } } }
输出：
Sorted Output: 1.0 8.0 9.0 11.0 12.0 13.0 17.0 19.0 21.0 24.0
桶排序的优缺点
| 优点 | 缺点 |
|---|---|
| 对均匀分布的数据执行更快的计算 | 与原地排序算法相比，它占用更多空间。 |
| 可用作大型数据集的外部排序方法 | 当数据分布不均匀时，性能不佳 |
| 桶可以独立且并行地处理。 | 需要预先了解数据范围和分布情况。 |
桶排序复杂度分析
桶排序时间复杂度
- 最佳情况复杂度： 如果数组中的所有元素均匀分布且在每个桶内预先排序，则将元素分散到相应的桶中需要 O(n) 时间。然后对每个桶进行排序，使用 插入排序 成本为 O(k)。因此，整体复杂度为 O(n+k)。
- 平均案例复杂度： 对于一般情况，我们假设输入数据均匀分布。因此，桶排序算法的时间复杂度为 O(n+k)，呈线性增长。其中，O(n) 的时间用于分散元素，O(k) 的时间用于使用插入排序对元素进行排序。
- 最坏情况复杂度： 最坏情况下，元素分布不均匀，集中在一个或两个桶中。在这种情况下，桶排序的行为会退化到类似于…… 冒泡排序算法因此，在最坏的情况下，桶排序的时间复杂度为 O(n²)。
桶排序的空间复杂度
桶排序的空间复杂度为 O(n*k)。其中，n 为元素个数，k 为排序时容纳这些元素所需的桶的数量。
