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) ② 快速排序是一个递归的过程,在排序过程中要用到栈。 ③ 从平均时间性能而言,快速排序最佳,其所用时间最少,但在最坏情况下的时间性能不如堆排序和归并排序 |
7.11 种内部排序算法的比较★4◎4
未经允许不得转载:7.11 种内部排序算法的比较★4◎4