设计与分析-桶排序

---

桶排序算法与计数排序算法类似，只是计数排序的推广形式。桶排序假设输入元素是从区间 [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 中，B[i]= $\lfloor$nA[i]$\rfloor$

步骤 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$