第七节 内部排序方法的分析比较

（1）直接插入、直接选择、冒泡排序算法的时间复杂度为O（n²）。

（2）快速、归并、堆排序算法的时间复杂度为O（nlog₂n）。

（3）希尔排序算法的时间复杂度很难计算，有几种较接近的答案：O（nlog₂n）或O（n^1.25）。

（4）基数排序算法的时间复杂度为O（d*（rd+n）），其中rd是基数，d是关键字的位数，n是元素个数。

2、稳定性

（1）直接插入、冒泡、归并和基数排序算法是稳定的；

（2）直接选择、希尔、快速和堆排序算法是不稳定的。

3、辅助空间（空间复杂度）

（1）直接插入、直接选择、冒泡、希尔和堆排序算法需要辅助空间为O（1）。

（2）快速排序算法需要辅助空间为O（log₂n）；

（3）归并排序算法需要辅助空间为O（n）：

（4）基数排序算法需要辅助空间为O（n+rd）。

4、选取排序方法时需要考虑的主要因素

（1）待排序的记录个数。

（2）记录本身的大小和存储结构。

（3）关键字的分布情况。

（4）对排序稳定性的要求。

（5）时间和空间复杂度等。

5、排序方法的选取

（1）若待排序的一组记录数目较小（如n≤50）时，可采用插入排序或选择排序。

（2）若n较大时，则应采用快速排序、堆排序或归并排序。

（3）若待排序记录按关键字基本有序时，则适宜选用直接插入排序或冒泡排序。

（4）当n很大，而且关键字位数较少时，采用链式基数排序较好。

（5）关键字比较次数与记录的初始排列顺序无关的排序方法是选择排序。

6、排序方法对记录存储方式的要求

一般的排序方法都可以在顺序结构（一维数组）上实现。当记录本身信息量较大时，为了避免移动记录耗费大量的时间，可以采用链式存储结构。例如插入排序、归并排序、基数排序易于在链表上实现，使之减少记录的移动次数，但有的排序方法，如快速排序、堆排序在链表上却难于实现，在这种请况下，可以提取关键字建立索引表，然后对索引表进行排序。

【真题选解】

本章小结

本章着重讨论有关内部排序的一些常用方法，主要有插入排序、交换排序、选择排序、归并排序及基数排序，介绍其排序思想、排序过程、算法实现时间和空间性能的分析及各种排序方法的比较和选择。

在掌握所介绍的几种主要排序算法的基本思想，同时还应该学会基本的算法分析技术，比较这些算法的时间和空间复杂性，从而能够在实际应用中正确选择适当的排序方法。