任务九：比较各排序方法

目前，已有的排序方法远远不止本项目讨论的这些方法，人们之所以热衷于研究多种排序方法，不仅是因为排序在计算机中所处的重要地位，还因为不同的方法各有其优缺点，从而可适用于不同的场合。选取排序方法时，需要考虑的因素有待排序的记录数目n、记录本身信息量的大小、关键字的结构及分布情况、对排序稳定性的要求、语言工具的条件和辅助空间的大小等。依据这些因素，可得出如下几点结论：

（1）若n较小（例如n≤50），可采用直接插入排序或直接选择排序。由于直接插入排序所需记录移动操作较直接选择排序多，因此，若记录本身信息量较大，则选用直接选择排序为宜。

（2）若文件的初始状态已是按关键字基本有序，则选用直接插入排序为宜。

（3）若n较大，则应采用的排序方法有快速排序、堆排序或归并排序。快速排序被认为是目前基于内部排序的最好的方法，当待排序的关键字随机分布时，快速排序的平均时间最少，但堆排序所需的辅助时间少于快速排序，并且不会出现序可能出现的最坏情况，这两种排序方法都是不稳定的。若要求排序稳定，则可以选用归并排序。但本书介绍的由单个记录进行两两归并的算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得子文件，然后再两两归并。因为直接插入排序是稳定的，所以改进后的归并排序是稳定的。

（4）在基于比较的排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以利用一棵二叉树来描述比较判定过程，由此可以证明：当文件的N个关键字随机分布时，任何借助于“比较”的排序算法，至少要O（nlgn）的时间，但由于桶排序和基数排序只需一步就会引起M种可能的转移，即把一个记录半装入M个箱子之一，因此，在一般情况下，桶排序和基数排序可能在O（n）时间内完成对N个记录的排序。但需要注意的是，桶排序和基数排序只适用于像字符串和整数这类有明显结构特征的关键字，当关键字的取值范围属于某个无穷集合时，无法使用桶排序和基数排序，这时只有借助“比较”方法来排序。由此可知，若N很大，记录的关键字位数较少且可以分解时，采用基数排序较好。

（5）前面讨论的几种排序算法中，除基数排序外，都是在一维数组上实现的。当记录本身信息量较大时，为了避免浪费大量时间来移动记录，可以用链表作为存储结构，如插入排序和归并排序都易于在链表上实现，并分别称为表和归并表。但有的方法，如快速排序和堆排序，在链表上难以实现，在这种情况下，可以通过提取关键字建立索引表，然后对索引表进行排序来排序。

前面讲到的排序方法按平均的时间性能来分，有三类排序方法：

①高效排序方法。时间复杂度为O（nlog2n） 的方法，有快速排序和堆排序，但实验结果表明，就平均时间性能而言，快速排序是所有排序方法中最好的。若待排序的记录个数n值较大，应选用快速排序法。但若待排序记录关键字有“有序”倾向，就慎用快速排序，而选用堆排序为宜。(www.xing528.com)

②简单排序方法。时间复杂度为O（n2）的方法，有插入排序和选择排序，其中插入排序最常用，特别是对于已按关键字基本有序排列的记录序列尤为如此，选择排序过程中的记录移动次数最少。简单排序方法一般只用于n较小的情况。当序列中的记录“基本有序”时，直接插入排序是最佳的排序方法，其常与快速排序和归并排序等其他排序方法结合使用。

③基数排序方法。时间复杂度为O（n）的排序方法，因此它最适用于n值很大而关键字的位数d较小的序列。

从平均时间性能来看，快速排序和归并排序有最好的时间性能。相对而言，快速排序速度最快。但快速排序在最坏情况下的时间性能达到了O（n2），比归并排序要差。

从空间性能来看，线性插入排序、折半插入排序、冒泡排序、选择排序要求的辅助空间较小，但时间性能较差。

从稳定性来看，除快速排序和选择排序是不稳定的外，其他的几种排序方法都是稳定的。

另外，从待排序记录的个数来看，当待排序记录的个数较少时，采用线性插入排序、折半插入排序或选择排序较好；当待排序记录的个数较多时，采用快速排序或归并排序较合适。

综上所述，每一种排序方法各有特点，没有哪一种方法是绝对最优的。在实际应用中，应根据具体情况来选择合适的排序方法，同时也可以将多种排序方法结合起来使用。