学科分类
目录
数据结构

内部排序方法比较

前面章节学习的多种排序算法都属于内部排序算法,参与排序的数据都存储在内存中。分析排序算法的性能,一般从算法的时间复杂度、空间复杂度和稳定性三方面着手。为了方便对比分析,在表1中列出了多种算法的在时间、空间以及稳定性方面的性能。

表1 内部排序性能表

分类 方法 时间复杂度 空间复杂度 稳定性
最好 最坏 平均
交换排序 冒泡排序 O(n) O(n2) O(n2) O(1) 稳定
快速排序 O(nlog2n) O(n2) O(nlog2n) O(nlog2n) 不稳定
插入排序 直接插入排序 O(n) O(n2) O(n2) O(1) 稳定
希尔排序 O(n1.3) O(1) 不稳定
选择排序 简单选择排序 O(n2) O(n2) O(n2) O(1) 不稳定
堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 不稳定
其它 归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n) 稳定
基数排序 O(d(r+n)) O(d(r+n)) O(d(r+n)) O(r) 稳定

表1中根据排序算法的特点将排序算法划分为交换排序、插入排序、选择排序和其它排序方法。

根据算法的平均时间性能,又可以将算法分为三类:

(1)平方阶算法,平均时间性能为O(n2)。这种算法一般又称为简单排序算法,如冒泡排序、直接插入排序,是典型的简单排序算法。这种算法对空间的要求不高,但是时间性能不稳定,其时间性能取决于原始序列与最终求解序列的差别。当原始序列基本有序时,这两种算法的时间性能达到最高。

(2)线性对数阶的算法,平均时间性能为O(nlog2n)。这种算法是较复杂的排序算法,如快速排序、堆排序和归并排序。从表1中可以看出,这几种排序算法的时间性能比较稳定,除了快速排序,其它两种算法的最好和最坏情况有相同的时间复杂度。这几种排序算法对空间的要求也不同,其中堆排序所需辅助空间最少,快速排序所需辅助空间最多。

(3)线性阶的算法,平均时间性能为O(n)。当参与排序的数据其位数d和基数r为常量时,基数排序就是一种线性阶的算法。

在排序算法中,冒泡排序是最早出现的排序算法,这个算法通过多轮比较,逐步调整数据在序列中的位置,在每一轮调整中除了能使本轮的最值到达合适的位置,还能使其它数据在序列中逐渐有序。简单选择排序算法也是一种初级算法,同样要经过多轮比较,相比与冒泡排序,这个算法减少了数据交换,但是每一轮排序只对本轮的最值进行操作,对其它数据没有影响。这两种算法都是平方阶算法,时间性能都比较差。

直接插入排序算法是对冒泡排序算法的改进,这个排序算法将待排序序列中的数据逐个插入有序序列中,插入新数据后的有序序列仍保持有序。它比冒泡排序快,但是提升并不明显,仍然是一个平方阶算法。通常也不将这个算法使用在数据量较大的场合。

希尔排序通过将原始序列分组,对每个组进行直接插入排序。它的时间性能高于直接插入排序,通常认为其平均时间性能为O(n1.3)。希尔排序算法是第一个使排序算法时间效率突破平方阶的算法。

快速排序是交换排序的一种,它是对冒泡排序的改进,快速排序再次使排序算法的时间性能有所突破。但是快速排序算法提高了对空间的要求,算法实现中使用递归思想,不适合处理超大量数据。

归并排序采用分治法思想,先将序列逐层分解成小的序列,再对不可再分的小序列进行排序,之后将有序的小序列合并,完成对序列的排序。但是这个算法需要的内存空间比较多,并且算法中涉及递归,同样不适合处理超大量数据。

堆排序首先将所有数据构建称一个堆,将数据中的最值放置在堆顶,然后将堆顶输出,将最后一个叶子结点放在堆顶,再调用调整算法使当前的堆重新成为一个大顶堆或小顶堆,再次输出堆顶,通过不断地循环调整与输出来为所有数据排序。堆排序是最高效的选择排序算法,它的时间性能非常稳定,并且对空间要求也很低,所以堆排序非常适合处理超大量的数据。

基数排序是表1中唯一一个时间复杂度为线性阶的排序算法,其中的d为记录中关键字的位数,r为每一位关键字的最大范围。只是若要使用基数排序,首先要先分析数据的存储格式,所以一般只用它处理整数或者其它数据格式明显的数据。

除去时间性能和空间性能,有些应用场景还对算法的稳定性有所要求,此时算法的性能还要取决于实际应用场景对算法各种性能的要求。

没有绝对好用的排序算法,在选择排序算法时,应结合实际情境,选择合适的排序算法。

点击此处
隐藏目录