excel箱单排序箱号 排序 - 分配排序 - 箱排序 （一）

排序 - 分配排序 - 箱排序 （一）  

　　按平均时间将排序分为四类

　　( )平方阶(O(n ))排序

　　一般称为简单排序 例如直接插入 直接选择和冒泡排序;

　　( )线性对数阶(O(nlgn))排序

　　如快速 堆和归并排序;

　　( )O(n +￡ )阶排序

　　￡是介于 和 之间的常数 即 <￡< 如希尔排序;

　　( )线性阶(O(n))排序

　　如桶 箱和基数排序

　　各种排序方法比较

　　简单排序中直接插入最好 快速排序最快 当文件为正序时 直接插入和冒泡均最佳

　　影响排序效果的因素

　　因为不同的排序方法适应不同的应用环境和要求 所以选择合适的排序方法应综合考虑下列因素

　　①待排序的记录数目n;

　　②记录的大小(规模);

　　③关键字的结构及其初始状态;

　　④对稳定性的要求;

　　⑤语言工具的条件;

　　⑥存储结构;

　　⑦时间和辅助空间复杂度等

　　不同条件下 排序方法的选择

　　( )若n较小(如n≤ ) 可采用直接插入或直接选择排序

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

　　( )若文件初始状态基本有序(指正序) 则应选用直接插人 冒泡或随机的快速排序为宜;

　　( )若n较大 则应采用时间复杂度为O(nlgn)的排序方法 快速排序 堆排序或归并排序

　　快速排序是目前基于比较的内部排序中被认为是最好的方法 当待排序的关键字是随机分布时 快速排序的平均时间最短;

　　堆排序所需的辅助空间少于快速排序 并且不会出现快速排序可能出现的最坏情况 这两种排序都是不稳定的

　　若要求排序稳定 则可选用归并排序 但本章介绍的从单个记录起进行两两归并的 排序算法并不值得提倡 通常可以将它和直接

　　插入排序结合在一起使用 先利用直接插入排序求得较长的有序子文件 然后再两两归并之 因为直接插入排序是稳定的 所以改进