9.9　7种排序方法的比较

通过本章对各种内部排序算法的讨论,各算法的特点可归纳如表9－1。

表9－1　7种排序方法的特点

分析上表,可得出以下结论。

（1）从平均性能而言,快速排序最佳,其时间最省,但在最坏情况下会蜕变成冒泡排序。当n较大时,归并排序所需时间较堆排序少,但所需辅助存储量最多。

（2）基数排序适用于n值很大而关键字较小的序列。

（3）从稳定性来看,除了基数排序、归并排序是稳定的以外,几乎所有性能较好的内部排序方法都是不稳定的。

（4）当序列中的记录“基本有序”或n值较小时,直接插入排序是最佳的排序方法,因此常将其与其他的排序方法,如快速排序、归并排序等结合使用。

各种内部排序方法之间的比较和选择,主要从以下方面综合考虑:时间复杂度；空间复杂度；稳定性；简单性；待排序记录数n的大小；记录本身信息量的大小等。依据上述在选择排序方法时需要考虑的因素,可以得出如下结论。

（1）若待排序记录数n较小,适合采用直接插入排序或简单选择排序。

（2）若待排序记录的初始状态已按关键字基本有序,适合采用选择直接插入排序或起泡排序。

（3）若待排序记录数n较大,关键字分布随机,并且稳定性要求不高,适合用快速排序。

（4）若待排序记录数n较大,内存空间允许,要求排序稳定时,可采用归并排序。

（5）若待排序记录数n较大,排序码分布可能出现正序或逆序的情况,并且对稳定性不做要求时,宜采用堆排序（或归并排序）。

本章小结

1.直接插入排序、起泡排序和简单选择排序是3种简单的排序方法,其平均时间复杂度都是O（n²）,空间复杂度是O（1）。但直接插入排序又优于简单选择排序,而简单选择排序又优于起泡排序。

2.快速排序、堆排序和归并排序是3种基本排序改进型的排序方法,平均复时间杂度都为O（nlog₂n）,空间复杂度分别为O（nlog₂n）、O（1）、O（n）。通常快速排序优于堆排序,而堆排序又优于归并排序。

3.直接插入排序、起泡排序和归并排序是稳定的排序方法,而直接插入排序、快速排序、堆排序是不稳定的排序方法。

4.本章所介绍的算法各有自身的优缺点,选用哪种排序的方法,需要根据具体的情况以及对时间、空间和稳定性的要求不同而定,甚至可以几种排序方法结合使用。