各种内部排序方法的比较讨论

对于这些内部排序方法之间的比较,主要从以下几个方面综合考虑:时间复杂度、空间复杂度、算法稳定性、算法简单性、待排序记录数n的大小、记录本身的信息量等

1 时间复杂度
选择n个整数组成一些随机排序,各种内部排序方法的实际时间如图7-10所示。

从时间复杂度看,所有内部排序方法可以分为两类。插入排序、选择排序和起泡排序这三种简单排序方法属于第一类,其时间复杂度为O(n^2);堆排序、快速排序和归并排序这三种排序方法属于第二类,其时间复杂度为O(nlog2n)。这是就平均情况而言的,如果从最好的情况考虑,则插入排序和起泡排序的时间复杂度最好,为O(n),而其他算法的最好情况同平均情况大致相同。如果从最坏的情况考虑,快速排序的时间复杂度为O(n^2),插入排序和起泡排序虽然同平均情况相同,但系数大约增加一倍,运行速度降低一半,而选择排序、堆排序和归并排序则影响不大。
总之,在平均情况下,快速排序最快;在最好情况下,插入排序和起泡排序最快;在最坏情况下,堆排序和归并排序最快。
2 空间复杂度
从空间复杂度看,归并排序属于第一类,其空间复杂度为O(n);快速排序属于第二类,其空间复杂度为O(nlog2n);其它排序方法归为第三类,其空间复杂度为O(1)。所以,第三类算法的空间复杂度最好,第二类次之,第一类最差。
3 算法稳定性
从算法稳定性看,所有内部排序方法可以分为两类。插入排序、起泡排序和归并排序属于第一类,是稳定的排序方法;选择排序、快速排序和堆排序属于第二类,是不稳定的排序方法。相对而言,后者的时间性能较好。
由于大多数情况下排序是按照记录的主关键字进行的,则所用的排序方法是否稳定无关紧要。但是如果排序是按照记录的次关键字进行的,则应根据问题需要慎重选择排序方法及其描述算法。
4 算法简单性
从算法简单性看,一类是简单算法,一般包括插入排序、选择排序和起泡排序,这些算法都比较简单和直接,易于理解;另一类是改进后的算法,一般包括堆排序、快速排序和归并排序,这些算法都比较复杂。当序列中的记录基本有序或者n值较小时,直接插入排序是最佳的排序方法,因此常常将它和其他的排序方法结合使用。
5 待排序记录数n的大小
从待排序的记录数n的大小看,n越小,n2和nlog2n越接近,采用简单排序方法越合适;n越大,采用改进排序方法越合适。另外,简单算法的输入和调试比改进算法的输入和调试要少用许多时间,如果也考虑这些时间,则n较小时选用简单算法比改进算法要节省时间。当n越大时,n2和nlog2n的差距越大,因此选用改进算法效果更明显。
6记录本身的信息量
从记录本身的信息量看,信息量越大占用的存储空间越大,移动记录时花费的时间越多,所以对记录的移动次数较多的算法不利。例如,在三种简单排序算法中,选择排序移动记录的次数为O(n),其他两种为O(n^2)。所以当记录本身的信息量较大时,对选择排序有利,而对其他两种算法不利。在三种改进算法中,记录本身的信息量较大时,对归并排序不利。
以上从六个方面对各种内部排序方法进行了分析和比较,那么在实际的排序问题中应如何考虑它们的主次呢?一般来说,首先考虑算法的稳定性,如果排序要求稳定,则只能在稳定的方法中选择,否则就可以选择任何的排序方法;其次要考虑待排序的记录数的大小,如果n较大,则在改进算法中选择,否则在简单算法中选择;然后再考虑其他的因素。


Comments are closed.