桶排序算法
桶排序算法与计数排序算法类似，因为它只是计数排序的广义形式。桶排序假设输入元素在区间 [0, 1) 上服从均匀分布。
因此，桶排序算法将区间 [0, 1) 划分为 n 个相等的部分，并将输入元素添加到索引为 桶 的桶中，其中索引基于 (n × 元素) 值的下限。由于该算法假设值是均匀分布在较小范围内的独立数字，因此不会有很多元素只落入一个桶中。
例如，让我们看一个元素输入列表：0.08、0.01、0.19、0.89、0.34、0.07、0.30、0.82、0.39、0.45、0.36。桶排序看起来像这样：−
桶排序算法
下面我们进一步看看这个算法是如何进行的：−
步骤 1 − 将区间分成 n 个相等的部分，每个部分称为一个桶。假设 n 为 10，则有 10 个桶；否则，桶的数量更多。
步骤 2 − 从输入数组 A 中取出输入元素，并根据计算公式 B[i]= $\lfloor$n.A[i]$ floor$ 将它们添加到输出桶 B 中。
步骤 3 −如果有任何元素被添加到已占用的存储桶中，则通过相应的存储桶创建一个链表。
步骤 4− 然后我们应用插入排序对每个存储桶中的所有元素进行排序。
步骤 5− 将这些存储桶连接在一起，然后获得输出。
伪代码
BUCKET-SORT(A) let B[0 … n – 1] be a new array n = A.length for i = 0 to n – 1 make B[i] an empty list for i = 1 to n insert A[i] into list B[$\lfloor$𝑛.𝐴[𝑖]$ floor$] for i = 0 to n – 1 sort list B[i] with insertion sort concatenate the lists B[0], B[1]; ………… ; B[n – 1] together in order
分析
桶排序算法假设输入元素相同，因此该算法的平均时间复杂度为 Θ(n)
示例
假设输入元素列表为 0.78、0.17、0.93、0.39、0.26、0.72、0.21、0.12、0.33、0.28，使用桶排序对这些元素进行排序 −
解决方案
步骤 1
从输入数组的索引"0"开始线性插入所有元素。也就是说，我们先插入 0.78，然后依次插入其他元素。插入元素的位置使用公式 − 计算得出。 B[i]= $\lfloor$n.A[i]$ floor$，即 $\lfloor$10 × 0.78$ floor$=7
现在，我们在索引 $\lfloor$10 × 0.17$ 处插入 0.17 floor$=1
步骤 3
将下一个元素 0.93 插入到输出桶中，位置为 $\lfloor$10 × 0.93$ floor$=9
步骤 4
使用公式 $\lfloor$10 × 0.39$ floor$=3 在索引 3 处插入 0.39
步骤 5
在输入数组中的位置 $\lfloor$10 × 0.26$ floor$=2 插入下一个元素 0.26
步骤 6
这里比较棘手。现在，输入列表中的下一个元素是 0.72，需要使用公式 $\lfloor$10 × 0.72$ floor$=7 将其插入到索引"7"处。但第 7 个存储桶中已经有一个数字。因此，需要从第 7 个索引创建一个链接，以链表的形式存储新数字，如下所示 −
步骤 7
以类似的方式，通过从所需的存储桶创建链表，将剩余的数字添加到存储桶中。但是，在将这些元素插入列表时，我们应用插入排序，即比较两个元素，并将最小值添加到前面，如下所示 −
步骤 8
现在，为了获得输出，将所有桶连接在一起。
0.12, 0.17, 0.21, 0.26, 0.28, 0.33, 0.39, 0.72, 0.78, 0.93
实现
桶排序算法的实现首先检索数组中的最大元素，并确定输出的桶大小。只需少量计算，即可将元素插入到这些桶中。
在本教程中，我们将使用四种编程语言执行桶排序。
#include <stdio.h>
void bucketsort(int a[], int n){ // 实现桶排序的函数
int max = a[0]; // 获取数组中的最大元素
for (int i = 1; i < n; i++)
if (a[i] > max)
max = a[i];
int b[max], i;
for (int i = 0; i <= max; i++) {
b[i] = 0;
}
for (int i = 0; i < n; i++) {
b[a[i]]++;
}
for (int i = 0, j = 0; i <= max; i++) {
while (b[i] > 0) {
a[j++] = i;
b[i]--;
}
}
}
int main(){
int a[] = {12, 45, 33, 87, 56, 9, 11, 7, 67};
int n = sizeof(a) / sizeof(a[0]); //n 是数组的大小
printf("排序前数组元素为：
");
for (int i = 0; i < n; ++i)
printf("%d ", a[i]);
bucketsort(a, n);
printf("
排序后数组元素为：
");
for (int i = 0; i < n; ++i)
printf("%d ", a[i]);
}
输出
排序前数组元素为： 12 45 33 87 56 9 11 7 67 排序后数组元素为： 7 9 11 12 33 45 56 67 87
#include <iostream>
using namespace std;
void bucketsort(int a[], int n){ // 实现桶排序的函数
int max = a[0]; // 获取数组中的最大元素
for (int i = 1; i < n; i++)
if (a[i] > max)
max = a[i];
int b[max], i;
for (int i = 0; i <= max; i++) {
b[i] = 0;
}
for (int i = 0; i < n; i++) {
b[a[i]]++;
}
for (int i = 0, j = 0; i <= max; i++) {
while (b[i] > 0) {
a[j++] = i;
b[i]--;
}
}
}
int main(){
int a[] = {12, 45, 33, 87, 56, 9, 11, 7, 67};
int n = sizeof(a) / sizeof(a[0]); // n 是数组的大小
cout << "排序前数组元素为：
";
for (int i = 0; i < n; ++i)
cout << a[i] << " ";
bucketsort(a, n);
cout << "
排序后数组元素为：
";
for (int i = 0; i < n; ++i)
cout << a[i] << " ";
}
输出
排序前数组元素为： 12 45 33 87 56 9 11 7 67 排序后数组元素为： 7 9 11 12 33 45 56 67 87
import java.io.*;
import java.util.*;
public class BucketSort {
static void bucketsort(int a[], int n) { // 实现桶排序的函数
int max = a[0]; // 获取数组中的最大元素
for (int i = 1; i < n; i++)
if (a[i] > max)
max = a[i];
int b[] = new int[max+1];
for (int i = 0; i <= max; i++) {
b[i] = 0;
}
for (int i = 0; i < n; i++) {
b[a[i]]++;
}
for (int i = 0, j = 0; i <= max; i++) {
while (b[i] > 0) {
a[j++] = i;
b[i]--;
}
}
}
public static void main(String args[]) {
int n = 9;
int a[] = {12, 45, 33, 87, 56, 9, 11, 7, 67};
System.out.println("排序前数组元素为：");
for (int i = 0; i < n; ++i)
System.out.print(a[i] + " ");
bucketsort(a, n);
System.out.println("
排序后数组元素为：");
for (int i = 0; i < n; ++i)
System.out.print(a[i] + " ");
}
}
输出
排序前数组元素为： 12 45 33 87 56 9 11 7 67 排序后数组元素为： 7 9 11 12 33 45 56 67 87
def bucketsort(a, n):
max_val = max(a)
b = [0] * (max_val + 1)
for i in range(n):
b[a[i]] += 1
j = 0
for i in range(max_val + 1):
while b[i] > 0:
a[j] = i
j += 1
b[i] -= 1
a = [12, 45, 33, 87, 56, 9, 11, 7, 67]
n = len(a)
print("排序前数组元素为：")
print(a)
bucketsort(a, n)
print("
排序后数组元素为：")
print(a)
输出
排序前数组元素为： [12, 45, 33, 87, 56, 9, 11, 7, 67] 排序后数组元素为： [7, 9, 11, 12, 33, 45, 56, 67, 87]
