数据结构：各种排序方法的综合比较

排序方法的选用应视具体场合而定。一般情况下考虑的原则有:(1)待排序的记录个数 n;(2)记录本身的大小;(3)关键字的分布情况:(4)对排序稳定性的要求等。

1.时间性能

(1) 按平均的时间性能来分,有三类排序方法:

时间复杂度为 O(nlogn)的方法有:快速排序、堆排序和归并排序,其中快速排序目前被认为是最快的一种排序方法,后两者比较,在n值较大的情况下,归并排序较堆排序更快。

时间复杂度为 O(n²)的有:插入排序、起泡排序和选择排序,其中以插入排序为最常用，特别是对于已按关键字基本有序排列的记录序列尤为如此,选择排序过程中记录移动次数最少。

时间复杂度为 O(n)的排序方法只有基数排序一种。

(2) 当待排记录序列按关键字顺序有序时,插入排序和起泡排序能达到 O(n)的时间复杂度;而对于快速排序而言,这是最不好的情况,此时的时间性能蜕化为 O(n²),因此应尽量避免。

(3) 选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变在大多数情况下,人们应事先对要排序的记录关键字的分布情况有所了解,才可对症下药，选择有针对性的排序方法。

(4) 以上对排序的时间复杂度的讨论主要考虑排序过程中所需进行的关键字间的比较次数,当待排序记录中其他各数据项比关键字占有更大的数据量时,还应考虑到排序过程中移动记录的操作时间,有时这种操作的时间在整个排序过程中占的比例更大,从这个观点考虑，简单排序的三种排序方法中起泡排序效率最低。

2.空间性能

空间性能指的是排序过程中所需的辅助空间大小。
(1) 所有的简单排序方法(包括: 插入、起泡和选择排序)和堆排序的空间复杂度均为O(1)
(2) 快速排序为 O(logn),为递归程序执行过程中栈所需的辅助空间
(3) 归并排序和基数排序所需辅助空间最多,其空间复杂度为 O(n)。

3.排序方法的稳定性能

(1) 稳定的排序方法指的是对于两个关键字相等的记录在经过排序之后,不改变它们在排序之前在序列中的相对位置。
(2) 除快速排序和堆排序是不稳定的排序方法外,其他排序方法都是稳定的。例如:对关键字序列(4¹,3,4²,2)进行快速排序,其结果为(2,3,4²,4¹)。
(3)“稳定性”是由方法本身决定的。一般来说,排序过程中所进行的比较操作和交换数据仅发生在相邻的记录之间,没有大步距的数据调整时,则排序方法是稳定的。

综合上述，可得下表：

由此,在选择排序方法时,可有下列几种选择:
(1) 若待排序的记录个数 n值较小(例如 n<30),则可选用插入排序法,但若记录所含数据项较多,所占存储量大时,应选用选择排序法。反之,若待排序的记录个数n值较大时应选用快速排序法。但若待排序记录关键字有“有序”倾向时,就慎用快速排序,而宁可选用归并排序或堆排序。
(2) 快速排序和归并排序在 n 值较小时的性能不及插入排序,因此在实际应用时,可将它们和插人排序“混合”使用。如在快速排序划分子区间的长度小于某值时。转而调用插入排序;或者对待排记录序列先逐段进行插入排序,然后再利用“归并操作”进行两两归并直至整个序列有序为止。
(3) 基数排序的时间复杂度为 O(dXn),因此特别适合于待排记录数 n 值很大,而关键字“位数 d”较小的情况。并且还可以调整“基数”(如将基数定为 100 或 1000 等)以减少基数排序的趟数 d 的值。
(4) 一般情况下,进行排序的记录的“排序码”各不相同,则排序时所用的排序方法是否稳定无关紧要。但在有些情况下的排序必须选用稳定的排序方法。例如，一组学生记录已按学号的顺序有序,由于某种需要,希望根据学生的身高进行一次排序,并且排序结果应保证相同身高的同学之间的学号具有有序性。显然,在对“身高”进行排序时必须选用稳定的排序方法。