Data Structures Algorithms 简明教程

Bucket Sort Algorithm

Bucket 排序算法类似于 Counting Sort 算法，因为它是计数排序的广义形式。Bucket 排序假设输入元素是从区间 [0, 1) 上的均匀分布中提取的。

The Bucket Sort algorithm is similar to the Counting Sort algorithm, as it is just the generalized form of the counting sort. Bucket sort assumes that the input elements are drawn from a uniform distribution over the interval [0, 1).

因此，Bucket 排序算法将区间 [0, 1) 划分为“n”个相等的部分，并将输入元素添加到索引存储桶中，其中索引基于 (n × 元素) 值的下限。由于该算法假设值是均匀分布在小范围内的独立数字，所以很少有元素仅落入一个存储桶中。

Hence, the bucket sort algorithm divides the interval [0, 1) into ‘n’ equal parts, and the input elements are added to indexed buckets where the indices based on the lower bound of the (n × element) value. Since the algorithm assumes the values as the independent numbers evenly distributed over a small range, not many elements fall into one bucket only.

例如，我们来看一个元素输入列表 0.08、0.01、0.19、0.89、0.34、0.07、0.30、0.82、0.39、0.45、0.36。Bucket 排序看起来像 −

For example, let us look at an input list of elements, 0.08, 0.01, 0.19, 0.89, 0.34, 0.07, 0.30, 0.82, 0.39, 0.45, 0.36. The bucket sort would look like −

Bucket Sort Algorithm

让我们看看这个算法将如何继续如下 −

Let us look at how this algorithm would proceed further below −

*步骤 1 *− 将区间划分为“n”个相等的部分，每个部分称为一个存储桶。如果 n 为 10，则有 10 个存储桶；否则更多。

*Step 1 *− Divide the interval in ‘n’ equal parts, each part being referred to as a bucket. Say if n is 10, then there are 10 buckets; otherwise more.

*步骤 2 *− 从输入数组 A 中获取输入元素，并根据计算公式 B[i]= $\lfloor$n.A[i]$\rfloor$ 将它们添加到这些输出存储桶 B 中

*Step 2 *− Take the input elements from the input array A and add them to these output buckets B based on the computation formula, B[i]= $\lfloor$n.A[i]$\rfloor$

*步骤 3 *− 如果有任何元素被添加到已占用的存储桶中，则通过相应的存储桶创建一个链表。

*Step 3 *− If there are any elements being added to the already occupied buckets, created a linked list through the corresponding bucket.

*步骤 4 *− 然后我们应用插入排序来对每个存储桶中的所有元素进行排序。

*Step 4 *− Then we apply insertion sort to sort all the elements in each bucket.

*步骤 5 *− 将这些存储桶串联在一起，然后得到输出。

*Step 5 *− These buckets are concatenated together which in turn is obtained as the output.

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 order

Analysis

Bucket 排序算法假设输入的恒等性，因此该算法的平均情况时间复杂度为 Θ(n)

The bucket sort algorithm assumes the identity of the input, therefore, the average case time complexity of the algorithm is Θ(n)

Example

考虑一个元素输入列表 0.78、0.17、0.93、0.39、0.26、0.72、0.21、0.12、0.33、0.28，使用 Bucket 排序对这些元素进行排序 −

Consider, an input list of elements, 0.78, 0.17, 0.93, 0.39, 0.26, 0.72, 0.21, 0.12, 0.33, 0.28, to sort these elements using bucket sort −

Solution

Step 1

从输入数组的索引“0”开始线性插入所有元素。也就是说，我们首先插入 0.78，然后按顺序插入其他元素。使用公式 − B[i]= $\lfloor$n.A[i]$\rfloor$，即，$\lfloor$10 ×0.78$\rfloor$=7 获得插入元素的位置

Linearly insert all the elements from the index ‘0’ of the input array. That is, we insert 0.78 first followed by other elements sequentially. The position to insert the element is obtained using the formula − B[i]= $\lfloor$n.A[i]$\rfloor$, i.e, $\lfloor$10 ×0.78$\rfloor$=7

现在，我们在索引 $\lfloor$10 ×0.17$\rfloor$=1 处插入 0.17

Now, we insert 0.17 at index $\lfloor$10 ×0.17$\rfloor$=1

Step 3

将下一个元素 0.93 插入输出存储桶中，位置为 $\lfloor$10 ×0.93$\rfloor$=9

Inserting the next element, 0.93 into the output buckets at $\lfloor$10 ×0.93$\rfloor$=9

Step 4

使用公式 $\lfloor$10 ×0.39$\rfloor$=3，在索引 3 处插入 0.39

Insert 0.39 at index 3 using the formula $\lfloor$10 ×0.39$\rfloor$=3

Step 5

在位置 $\lfloor$10 ×0.26$\rfloor$=2 插入输入数组中的下一个元素 0.26

Inserting the next element in the input array, 0.26, at position $\lfloor$10 ×0.26$\rfloor$=2

Step 6

这里开始变得棘手. 输入列表中的下一个元素是 0.72，它需要使用公式 $\lfloor$10 ×0.72$\rfloor$=7 插入到索引“7”。但是，第 7 个存储槽中已经有一个数字了。所以，从第 7 个索引创建一个链接来存储新数字，就像一个链表，如下所示 −

Here is where it gets tricky. Now, the next element in the input list is 0.72 which needs to be inserted at index ‘7’ using the formula $\lfloor$10 ×0.72$\rfloor$=7. But there’s already a number in the 7th bucket. So, a link is created from the 7th index to store the new number like a linked list, as shown below −

Step 7

以类似的方式将余下数字添加到存储槽中，方法是从所需的存储槽创建链表。但是在将这些元素作为列表插入时，我们应用插入排序，即比较两个元素并在前面添加最小值，如下所示 −

Add the remaining numbers to the buckets in the similar manner by creating linked lists from the desired buckets. But while inserting these elements as lists, we apply insertion sort, i.e., compare the two elements and add the minimum value at the front as shown below −

Step 8

现在，为了获得输出，将所有存储槽连接在一起。

Now, to achieve the output, concatenate all the buckets together.

0.12, 0.17, 0.21, 0.26, 0.28, 0.33, 0.39, 0.72, 0.78, 0.93

Implementation

桶排序算法的实现首先检索数组的最大元素并确定输出的存储槽大小。根据一些计算将元素插入到这些存储槽中。

The implementation of the bucket sort algorithm first retrieves the maximum element of the array and decides the bucket size of the output. The elements are inserted into these buckets based on few computations.

在本教程中，我们用四种编程语言执行桶排序。

In this tutorial, we execute bucket sort in four programming languages.