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