7.11 种内部排序算法的比较★4◎4

　　7.11 各种内部排序算法的比较★4◎4

　　排序在计算机程序设计中非常重要，7.3～7.10节介绍的排序方法各有优缺点，适用的场合也各不相同。在选择排序方法时应考虑的因素有：
　　（1）待排序记录的数目n的大小；
　　（2）记录本身除关键码以外的其他信息量的大小；
　　（3）关键码的情况；
　　（4）对排序稳定性的要求；
　　（5）语言工具的条件，辅助空间的大小等。
　　综合考虑以上因素，可以得出如下结论：
　　（1）若排序记录的数目n较小（如n≤50）时，可采用直接插入排序或简单选择排序。由于直接插入排序所需的记录移动操作比简单选择排序多，因此当记录本身信息量较大时，用简单选择排序比较好。
　　（2）若记录的初始状态已经按关键码基本有序，可采用直接插入排序或冒泡排序。
　　（3）若排序记录的数目n较大，则可采用时间复杂度为O(nlog2n)的排序方法（如快速排序、堆排序或归并排序等）。快速排序的平均性能最好，若待排序序列已经按关键码随机分布时，快速排序最适合。快速排序在最坏情况下的时间复杂度是O(n2)，而堆排序在最坏情况下的时间复杂度不会发生变化，并且所需的辅助空间少于快速排序。但这两种排序方法都是不稳定的排序，若需要稳定的排序方法，则可采用归并排序。
　　（4）基数排序可在O(d×n)（d为关键码的个数，n为待排序记录的数目）时间内完成对n个记录的排序，但基数排序只适合于字符串和整数这种有明显结构特征的关键码。当n很大、d较小时，可采用基数排序。
　　（5）前面讨论的排序算法，除基数排序外，其他排序算法都是采用顺序存储结构。当待排序的记录非常多时，为避免花大量的时间进行记录的移动，可以采用链式存储结构。直接插入排序和归并排序都可以非常容易地在链表上实现，当快速排序和堆排序却很难在链表上实现。此时，可以提取关键码建立索引表，然后对索引表进行排序；也可以引入一个整形数组t[n]作为辅助表，排序前使t[i]=i，1≤i≤n。若排序算法中要求交换记录R[i]和R[j]，则只需交换t[i]和t[j]即可。排序结束后，数组t[n]就存放了记录之间的顺序关系。
　　各排序算法的比较如表7-2所示。

表7-2 各排序算法的比较

排序方法	最好情况下时间复杂度	最坏情况下时间复杂度	平均时间 　　 复杂度	辅助空间	稳  定  性	备    注
插入排序	O(n)	O(n2)	O(n2)	O(1)	√	当序列基本有序时，插入排序是最佳的排序算法
希尔排序				O(1)	×
冒泡排序	O(n2)	O(n2)	O(n2)	O(1)	√
选择排序	O(n2)	O(n2)	O(n2)	O(1)	√	无论初始序列如何，记录的比较次数不受影响
堆排序				O(1)	×
归并排序				O(n)	√	无论初始序列如何，记录的比较次数不受影响
基数排序	O(d(n+rd))	O(d(n+rd))	O(d(n+rd))	O(rd)	√	待排序列为n个记录，d个关键码，关键码的取值范围为rd

续表

排序方法	最好情况下时间复杂度	最坏情况下时间复杂度	平均时间 　　 复杂度	辅助空间	稳  定  性	备注
快速排序		O(n2)			×	① 当初始序列有序或基本有序时，其蜕化为冒泡排序。时间复杂度为O(n2) ② 快速排序是一个递归的过程，在排序过程中要用到栈。 ③ 从平均时间性能而言，快速排序最佳，其所用时间最少，但在最坏情况下的时间性能不如堆排序和归并排序