【答案解析】各种排序算法的比较见下表。
排序算法比较
|
|
排序方法
|
最好时间
|
平均时间
|
最坏时间
|
辅助存储
|
稳定性
|
备 注
|
|
简单选择排序
|
O(n
2
)
|
O(n
2
)
|
O(n
2
)
|
O(1)
|
不稳定
|
n小时较好
|
|
直接插入排序
|
O(n)
|
O(n
2
)
|
O(n
2
)
|
O(1)
|
稳定
|
大部分已有序时较好
|
|
冒泡排序
|
O(n)
|
O(n
2
)
|
O(n
2
)
|
O(1)
|
稳定
|
n小时较好
|
|
希尔排序
|
O(n)
|
O(nlogn)
|
O(n
s
)1＜s＜2
|
O(1)
|
不稳定
|
s是所选分组
|
|
快速排序
|
O(nlogn)
|
O(nlogn)
|
O(n
2
)
|
O(logn)
|
不稳定
|
n大时较好
|
|
堆排序
|
O(nlogn)
|
O(nlogn)
|
O(nlogn)
|
O(1)
|
不稳定
|
n大时较好
|
|
归并排序
|
O(nlogn)
|
O(nlogn)
|
O(nlogn)
|
O(n)
|
稳定
|
n大时较好
|
从该表中可以得到以下几个方面的结论：
1)简单地说，所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，就称这种排序方法是稳定的，反之就是非稳定的。例如，一组数排序前是a1，a2，a3，a4，a5，其中a2=a4，经过某种排序后为a1，a2，a4，a3，a5，则说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1，a4，a2，a3，a5就不是稳定的了。各种排序算法中稳定的排序算法有直接插入排序、冒泡排序和归并排序，而不稳定的排序算法有希尔排序、快速排序、简单选择排序和堆排序。
2)时间复杂度为O(n
2
)的排序算法有直接插入排序、冒泡排序、快速排序和简单选择排序，时间复杂性为O(nlogn)的排序算法有堆排序和归并排序。
3)空间复杂度为O(1)的算法有简单选择排序、直接插入排序、冒泡排序、希尔排序和堆排序，空间复杂杂度为O(n)的算法是归并排序，空间复杂度为O(logn)的算法是快速排序。
4)虽然直接插入排序和冒泡排序的速度比较慢，但是当初始序列整体或局部有序时，这两种排序算法会有较好的效率。当初始序列整体或局部有序时，快速排序算法的效率会下降。当排序序列较小且不要求稳定性时，直接选择排序效率较好；要求稳定性时，冒泡排序效率较好。
除了以上这几种排序算法以外，还有位图排序、桶排序、基数排序等。每种排序算法都有其最佳适用场合。例如，当待排序数据规模巨大，而对内存大小又没有限制时，位图排序则是最高效的排序算法。所以，在选择使用排序算法的时候，一定要结合实际情况进行分析。