|
按平均时间将排序分为四类 ()平方阶(O(n ))排序 一般称为简单排序例如直接插入直接选择和冒泡排序; ()线性对数阶(O(nlgn))排序 如快速堆和归并排序; ()O(n +￡ )阶排序 ￡是介于和之间的常数即<￡<如希尔排序; ()线性阶(O(n))排序 如桶箱和基数排序 各种排序方法比较 简单排序中直接插入最好快速排序最快当文件为正序时直接插入和冒泡均最佳 影响排序效果的因素 因为不同的排序方法适应不同的应用环境和要求所以选择合适的排序方法应综合考虑下列因素 ①待排序的记录数目n; ②记录的大小(规模); ③关键字的结构及其初始状态; ④对稳定性的要求; ⑤语言工具的条件; ⑥存储结构; ⑦时间和辅助空间复杂度等 不同条件下排序方法的选择 ()若n较小(如n≤)可采用直接插入或直接选择排序 当记录规模较小时直接插入排序较好;否则因为直接选择移动的记录数少于直接插人应选直接选择排序为宜 ()若文件初始状态基本有序(指正序)则应选用直接插人冒泡或随机的快速排序为宜; ()若n较大则应采用时间复杂度为O(nlgn)的排序方法快速排序堆排序或归并排序 快速排序是目前基于比较的内部排序中被认为是最好的方法当待排序的关键字是随机分布时快速排序的平均时间最短; 堆排序所需的辅助空间少于快速排序并且不会出现快速排序可能出现的最坏情况这两种排序都是不稳定的 若要求排序稳定则可选用归并排序但本章介绍的从单个记录起进行两两归并的 排序算法并不值得提倡通常可以将它和直接 插入排序结合在一起使用先利用直接插入排序求得较长的有序子文件然后再两两归并之因为直接插入排序是稳定的所以改进 后的归并排序仍是稳定的 |
