Data Structures Algorithms 简明教程
Bucket Sort Algorithm
Bucket 排序算法类似于 Counting Sort 算法，因为它是计数排序的广义形式。Bucket 排序假设输入元素是从区间 [0, 1) 上的均匀分布中提取的。
因此，Bucket 排序算法将区间 [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。Bucket 排序看起来像 −
Bucket Sort Algorithm
让我们看看这个算法将如何继续如下 −
*步骤 1 *− 将区间划分为“n”个相等的部分，每个部分称为一个存储桶。如果 n 为 10，则有 10 个存储桶；否则更多。
*步骤 2 *− 从输入数组 A 中获取输入元素，并根据计算公式 B[i]= $\lfloor$n.A[i]$\rfloor$ 将它们添加到这些输出存储桶 B 中
*步骤 3 *− 如果有任何元素被添加到已占用的存储桶中，则通过相应的存储桶创建一个链表。
*步骤 4 *− 然后我们应用插入排序来对每个存储桶中的所有元素进行排序。
*步骤 5 *− 将这些存储桶串联在一起，然后得到输出。
Pseudocode
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$𝑛.𝐴[𝑖]$\rfloor$]
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 orderSolution
Step 1
从输入数组的索引“0”开始线性插入所有元素。也就是说，我们首先插入 0.78，然后按顺序插入其他元素。使用公式 − B[i]= $\lfloor$n.A[i]$\rfloor$，即，$\lfloor$10 ×0.78$\rfloor$=7 获得插入元素的位置
现在，我们在索引 $\lfloor$10 ×0.17$\rfloor$=1 处插入 0.17
Step 3
将下一个元素 0.93 插入输出存储桶中，位置为 $\lfloor$10 ×0.93$\rfloor$=9
Step 4
使用公式 $\lfloor$10 ×0.39$\rfloor$=3，在索引 3 处插入 0.39
Step 5
在位置 $\lfloor$10 ×0.26$\rfloor$=2 插入输入数组中的下一个元素 0.26
Step 6
这里开始变得棘手. 输入列表中的下一个元素是 0.72，它需要使用公式 $\lfloor$10 ×0.72$\rfloor$=7 插入到索引“7”。但是，第 7 个存储槽中已经有一个数字了。所以，从第 7 个索引创建一个链接来存储新数字，就像一个链表，如下所示 −
Step 7
以类似的方式将余下数字添加到存储槽中，方法是从所需的存储槽创建链表。但是在将这些元素作为列表插入时，我们应用插入排序，即比较两个元素并在前面添加最小值，如下所示 −
Step 8
现在，为了获得输出，将所有存储槽连接在一起。
0.12, 0.17, 0.21, 0.26, 0.28, 0.33, 0.39, 0.72, 0.78, 0.93