首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》选择排序算法的标准

关灯直达底部

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

在为不同的数据选择合适的算法的时候,你需要知道输入数据的一些性质。我们创建了一些基准测试数据来比较本章所讲述的算法。注意表中的实际值是并不重要的,因为它们和基准测试运行的硬件相关。然而,你需要注意算法在这些数据集合的相对性能。

随机字符串

通过本章的论述,给定n!个字符串,或者大约4.03*1026个字符串,并且这些字符串很少重复,不仅如此,比较元素的开销不是常数。因为有时候会需要比较多个字符。通过计算这样的数据,我们可以知道明白了当排序26个字母的字符串时各个排序算法的性能。

双精度的浮点值

使用在大多数操作系统上可用的伪随机数生成器,我们得到了一系列范围在[0,1)的随机数。在这个数据集合中基本上没有重复的元素,比较两个元素的开销是一个固定的常数。

给排序算法的输入数据可以被预处理,为了确保以下性质(并不是都相容的)。

有序

输入数据可是预先有序的,降序或者升序(最终目的)。

三中值方法的反例

Musser(1997)发现了一个排列的顺序,这个顺序能够确保快速排序在使用三中值选择中枢值的时候需要O(n2)次比较。

几乎有序

给定一个有序的数据,我们选择相距d的k对元素进行交换(如果d为0则表示任意两个元素能够交换)。这样就能够构造一个和输入很相似的数据。

接下来的表中的列是按照算法在表最后一行的性能表现从左到右排好序。每一节有四个表,分别表明在本章早些描述的四种情况下的性能。

综合分析基准测试结果

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