数据结构与算法分析：你真的理解排序算法吗——总结

一、选择排序算法的标准

选择一个排序算法时，考虑下表的定性标准。这些标准可能能够帮你做出最初的决定，但是你需要更多量化标准作为指引。

在为不同的数据选择合适的算法的时候，你需要知道输入数据的一些性质。我们创建了一些基准测试数据来比较本章所讲述的算法。注意表中的实际值是并不重要的，因为它们和基准测试运行的硬件相关。然而，你需要注意算法在这些数据集合的相对性能。
随机字符串：
通过这段时间的讲述,给定n!个字符串,或者大约4.03*1026个字符串,并且这些字符串
很少重复,不仅如此,比较元素的开销不是常数。因为有时候会需要比较多个字
符。通过计算这样的数据,我们可以知道明白了当排序26个字母的字符串时各个排
序算法的性能。
双精度的浮点值：
使用在大多数操作系统上可用的伪随机数生成器,我们得到了一系列范围在[0,1)的
随机数。在这个数据集合中基本上没有重复的元素,比较两个元素的开销是一个固
定的常数。
给排序算法的输入数据可以被预处理,为了确保以下性质(并不是都相容的)。
有序：
输入数据可是预先有序的,降序或者升序(最终目的)。
三中值方法的反例：
Musser(1997)发现了一个排列的顺序,这个顺序能够确保快速排序在使用三中值
选择中枢值的时候需要O(n2)次比较。
几乎有序：
给定一个有序的数据,我们选择相距d的k对元素进行交换(如果d为0则表示任意两
个元素能够交换)。这样就能够构造一个和输入很相似的数据。
接下来的表中的列是按照算法在表最后一行的性能表现从左到右排好序。

二、综合分析基准测试结果

因为插入排序和选择排序是本章中在随机均匀数据(提升一些数量级)最慢的两个算法,所以我们在下面忽略这两个算法。但是,这两个算法值得处理有序数据和几乎有序数据。插大排序比其他算法表现要好,通常要快一个数量级。为了得到下表的结果,我们在高端计算机上执行了100次实验,抛弃最好和最坏的结果,把剩下的98次结果的平均值填在表中。标记为QuicksortBFPRT minSize=4的列表示一个快速排序的实现,它使用了BFPRT(集合大小为4)来选择切分值,并且在子数组规模少于4个元素的时候切换到插人排序。
在基于26个字母随机生成转置排序上的结果：

在基于26个字母随机生成的有序转置排序的结果：

在对中值选择最不利的数据上进行排序的结果：

因为三中值快速排序速度退化的厉害，因此只进行了10次实验，表中所示的是最好的和最坏的情况去除以后，8次运行的平均值。
在随机交换16对相距8个位置的元素的数据上排序的结果：

在随机交换n/4对相距4个位置的元素的数据上排序的结果：

三、双浮点数基准测试结果

使用双浮点数的基准测试，消除了很多字符串比较的时候产生的总开销，我们再一次在下表中忽略了插入排序和选择排序：
排序随机浮点数的算法性能：

排序有序浮点数的算法性能：

在对中值选择最不利的数据上进行排序的结果：

在随机交换16对相距8个位置的元素的数据上排序的结果：

在随机交换n/4对相距4个位置的元素的数据上排序的结果：

四、总结

关于排序算法的讲解到此就结束了，后面在专栏中我们将开始讲解查找相关的算法。