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

54

第

4

章

排序算法

通过合理的排序预处理，大量的计算任务和作业变得简单。在计算机发展早期，研究人

员将大部分精力放在寻找高效的排序算法上。事实上，很多早期的算法研究都关注于大

数据量的排序，因为早期计算机的内存有限，无法完整地存储那些数据。相比

50

年前的

计算机，现代计算机的能力要强大得多，现今处理的数据量已经达到了太字节（

Terabyte

）

的级别。尽管不需要手工排序如此海量的数据集，但还是有可能需要对一些略大一点的

数据集进行排序。本章将介绍一些最重要的排序算法，并给出它们的性能评测结果，以

此来帮助读者在各种场景下选择最佳的排序算法。

4.1 概述

4.1.1 术语

已知数据集合

A

中的元素可两两比较，现需要对

A

进行排序。我们用

A

[

i

]

和

a

i

表示这个

集合中的第

i

个元素。按照惯例，集合中的第一个元素被记作

A

[0]

。我们使用

A

[

low

,

low

+

n

)

表示包含

n

个元素的子集合

A

[

low

]

到

A

[

low

+

n

－

1]

。注 意 ，

A

[

low

,

low

+

n

]

包含

n

+ 1

个元素。

要排序一个集合，就必须重新组织

A

中的元素以满足如下条件：如 果

A

[

i

] <

A

[

j

]

，就 有

i

<

j

。

如果有重复的元素，那么在结果集合中，这些重复的元素就必须连续地出现。也就是说，

在一个有序的集合中，如果

A

[

i

] =

A

[

j

]

，那么不存在

k

，满足

i

<

k

<

j

并且

A

[

i

]

≠

A

[

k

]

。

最终，排完序的集合

A

必然是原有集合

A

元素的一个排列。

4.1.2 表示方式

待排序的集合可能已经存储在计算机的随机存储器（

RAM

）中，也有可能只是存储在文 ...