15.1. 排序算法的实验比较
哪种排序算法最快？渐近复杂度分析让我们能够区分 \(\Theta(n^2)\)
算法与 \(\Theta(n \log n)\) 算法，但它无助于区分具有相同渐近复杂度
的算法。
渐近分析也没有说明哪种算法最适合排序小规模线性表。
要回答这些问题，我们可以求助于实验测试。
表 8.15.1 给出了本章所介绍的排序算法实际实现的计时结果。
参与比较的算法包括
插入排序 ，
冒泡排序 ，
选择排序 ，
希尔排序 ，
快速排序 ，
归并排序 ，
堆排序 ，
基数排序 ，
它们全都运行在简单的 int[] 数组上。
插入排序计时的有两个版本：标准算法，以及用移位把值沿数组下移而非
简单交换的优化版本。
冒泡排序给出了标准算法和另一个会监视最后交换位置以尝试优化性能的
版本的时间。
归并排序比较了基于数组的基本实现和优化版本（对长度低于阈值 14 的
线性表改为调用插入排序）。
对快速排序，比较了两个版本：基本实现，以及不对长度低于 14 的
子线性表进行划分（最后再执行插入排序）的优化版本。
基数排序给出了三个版本的时间：基于数组的版本（一个用除法和取模，
另一个用移位和掩码）以及链表版本（用除法和取模）。
除最右边的几列之外，每个算法的输入都是随机的整数数组。
这会影响某些排序算法的计时。
例如，选择排序没有得到最有利的使用，因为记录很小（交换代价低），
所以它无法展现出最好的表现。
基数排序的实现当然利用了它知道键是整数这一点，不会查看超出
必要范围的位。
各种排序算法针对长度为 10、100、1000、10,000、100,000 和 1,000,000
的线性表给出了结果。
（注意， \(O(n^2)\) 排序没有给出长度为 1,000,000 的输入数组的
时间，因为它们所需时间过长。）
每个表的最后两列分别给出算法在长度为 10,000、数字呈升序（已排序）
和降序（逆序）的输入上的性能。
这两列展示了某些算法的最好情况性能，以及其他算法的最坏情况性能。
它们还表明，对某些算法而言，输入的顺序几乎没有影响。
这些数据揭示了一些有趣的结果。
正如预期， \(O(n^2)\) 排序在大数组上表现相当差。
插入排序显然是这一组中最好的。
对于哪怕只有 100 条记录的线性表，希尔排序也明显优于任何这些
\(O(n^2)\) 排序。
除基数排序之外，优化后的快速排序通常是整体最佳的算法。
即便对小数组，优化后的快速排序也表现良好，因为它在调用插入排序
之前先做一次划分。
与其他 \(O(n \log n)\) 排序相比，未优化的堆排序相当慢，原因是
类结构的空间开销。
当把这一切都剥离、让算法直接操作数组来实现时，它仍然比归并排序
稍慢一些。
一般来说，对各种算法进行优化会给较大的数组规模带来明显改进。
总体而言，基数排序的表现出人意料地强劲。
基于数组的版本和链表版本都是如此。
然而，它要求能够正确地操作键的各个数位，这可能限制该排序所能
支持的记录类型（因而也限制其应用）的范围。
当然，重要的是要考虑到上面这些排序时间是针对简单的 int 值数组的。
这会影响键值访问与比较所需的相对时间，以及交换时间。
表 8.15.1 给出了同一组算法在改写为支持键值对
（Key-Value Pair）对象记录（其中键和值都是 Integer 对象）时的
计时结果。
少数算法的相对表现变好或变差。
最明显的变化是，快速排序和归并排序的优化版本运行时间实际上相同。
下面是一些选择题，要求你比较本章学过的排序算法。
