算法技术手册（原书第2 版）

排序算法

｜

75

排序算法

均匀分布

输入数据需要均匀分布在一个给定的范围内。算法会基于这种数据分布创建

n

个桶

来对给输入范围内的数据均匀分配。

有序散列函数

桶必须是有序的。如果

i

<

j

，桶

b

i

中的元素要字典序小于桶

b

j

中的元素。

桶排序算法小结

最好情况、平均情况和最坏情况的性能：

O

(

n

)

sort (A)

create n buckets B

for i = 0 to n-1 do

❶

k = hash(A[i])

add A[i] to the k-th bucket B[k]

extract (B, A)

❷

end

extract (B, A)

idx = 0

for i = 0 to n-1 do

insertionSort (B[i])

❸

foreach element e in B[i]

❹

A[idx++] = e

end

❶

创建桶列表，将所有元素散列到正确的桶。

❷

处理所有的桶，提取数据并按照有序的方式放回

A

。

❸

如果桶中多于一个元素，先行对该桶进行排序。

❹

将元素复制回

A

中正确的位置。

桶排序

不适合排序随机字符串，这是因为通常不可能开发出一个具备所需特征的散列函

数。但是，它能够用于排序在区间

[0, 1)

之间均匀分布的浮点数。

一旦所有待排序的元素都被放入桶中，

桶排序

会从左至右对每个桶中的值使用

插入排序

。

每一个桶中的元素按照顺序从左至右提取出来重新构造原始的数组。示例执行过程如图

4-9

所示。