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

排序算法

｜

79

排序算法

值会从桶中提取出来并写回到输入数组中。当一个桶中包含多个元素时，需要采用

插入

排序

对桶内元素进行排序。对于表现出

O(

n

)

性能的桶排序，我们需要保证排序每个桶所

花费的总时间为

O(

n

)

。我们定义

n

i

是分到桶

b

i

的元素数目。我们可以把

n

i

看作随机变量（使

用统计理论）。现在考虑

n

i

的期望值

E

[

n

i

]

。输入中的每一个元素插入一个给定的桶中的

概率为

1/

p

，因为每个元素的值是从

[0,1)

之间均匀提取的。因此

E

[

n

i

] =

n

*

p

=

n

*

(1/

n

) = 1

，

方差

Var

[

n

i

] =

n

*

p

*

(1

－

p

) = (1

－

1/

n

)

。考虑方差是非常重要的，因此有些桶可能是空的，

而其他的可能有多于

1

个元素。我们需要保证没有桶包含过多的元素。通过统计理论，

可以得到如下的随机变量等式：

E

[

n

i

2

] =

Var

[

n

i

]+

E

2

[

n

i

]

这个等式计算出了

n

i

2

的期望值。这个计算非常关键，因为它决定了插入排序的费用，而

在最坏情况下，插入排序的性能为

O(

n

2

)

。进一步计算可以得到，

E

[

n

i

2

]=(1

－

1/

n

) + 1= (2

－

1/

n

)

，也就是说，

E

[

n

i

2

]

可以被认为是一个常数。这意味着在

n

个桶上执行插入排序的

总费用加起来之后，总的期望性能为

O(

n

)

。

4.7.3 衍生算法

散列排序

创建了数量相对更多的

k

个桶（而不是

n

个桶）来分配元素。随着

k

的增长，

散列排序的性能会不断提升。

散列排序

的关键之处在于

散列函数

hash(e)

返

回的整数值。

对于每个元素

e

，如果

a

i

≤

a

j

，就有

hash

(

a

i

)

≤