[AS3]as3排序方法和算法(2)

三、排序方法的选择

因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法很重要

(1)若n较小，可采用直接插入或直接选择排序。
当记录规模较小时，直接插入排序较好，它会比选择更少的比较次数；
但当记录规模较大时，因为直接选择移动的记录数少于直接插人，所以宜用选直接选择排序。
这两种都是稳定排序算法。

(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜(这里的随机是指基准取值的随机，原因见上的快速排序分析)；这里快速排序算法将不稳定。

(3)若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。
快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
堆排序虽不会出现快速排序可能出现的最坏情况。但它需要建堆的过程。这两种排序都是不稳定的。
归并排序是稳定的排序算法，但它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。

(4)特殊的箱排序、基数排序
它们都是一种稳定的排序算法，但有一定的局限性：
1>关键字可分解。
2>记录的关键字位数较少，如果密集更好
3>如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排序。