排序算法的选择

面对各种各样的排序算法，在实际应用 中，应该如何选择呢？

选择基准 对于本章介绍的这些常用排序算法，每种算法都有其优缺点，根据其特点可适应于不同的场合。要判断一个算法的优劣，可 从以下几方面来进行考虑。 

1、计算的复杂度：分为最差、平均和最好3种情况进行考虑，依据排序数据量的大小（n）。一般而言，好的表现是 O（nlogn），最差表现为O（n^2 ）。

2、系统资源的使用：包括计算机内存以及其他资源的使用。

3、稳定度：稳定排序算法会依照相等的关键字维持记录的相对次序。就是说，如果一个排序算法是稳定的，当有两个有相等 关键字的记录A和B，在待排序的数据中A出现在B之前，在排序过后的数据中A也应该在B之前。

1．计算的复杂度：

一般地，计算算法的复杂度就是考察其执行速度，可考察平均执行速度和最坏情况下的执行速度两种情况。下面列出各种算 法的计算复杂度（在下面列出的数据中，n表示需要排序元素的数量）。

1.1、冒泡排序法，平均速度和最坏情况下的速度都为O（n^ 2 ）；

1.2、快速排序法，平均速度为O（nlogn），比冒泡排序法要快，但在最坏情况下的速度与冒泡排序法相同，为O（n^2 ）；

1.3、简单选择排序法，平均速度和最坏情况下的速度都为O（n^ 2 ）；

1.4、堆排序法，平均速度和最坏情况下的速度都为O（nlogn）；

1.5、直接插入排序法，平均速度和最坏情况下的速度都为O（n^ 2 ）；

1.6、希尔排序法，平均速度为O（n 3/2 ），最坏情况下的速度为O（n^ 2 ）；

1.7、合并排序法，平均速度和最坏情况下的速度都为O（nlogn）。

2、稳定度 

下列排序算法是稳定的： 

冒泡排序法、插入排序法、合并排序法。 

而下列排序算法是不稳定的： 

选择排序法、希尔排序法、堆排序法、快速排序法。

3、各种排序算法的优缺点 

没有某一种排序算法是绝对最好的，在不同的情况下，需要选择不同的排序算法。

下面列出部分情况下可选用的排序算法： 

当数据为正序时，使用直接插入排序法、冒泡排序法和快速排序法。

若n值较小（如n≤50），可采用直接插入排序法或直接选择排序法。

当记录规模较小时，直接插入排序较好；否则因为直接 选择移动的记录数少于直接插入，应选直接选择排序为宜。

若n值较大，则应采用时间复杂度为O（nlogn）的排序方法，如快速排序、堆排序或归并排序。

当待排序的关键字是随机分布时，快速排序的平均时间最短。

若要求排序稳定，则可选用合并排序。 

注意 一般测试数据均是保存在一个数组中。当需排序的数据规模较大时，为避免耗费大量的时间去移 动数据，可以用链表作为存储结构。但有的排序方法，如快速排序和堆排序，在链表上却难以实现，需采用其他方法进行处理。