(1)选取排序方法需要考虑的因素
1)待排序的元素数目n。
2)元素本身信息量的大小。
3)关键字的结构及其分布情况。
4)稳定性的要求。
5)语言工具的条件,存储结构及辅助空间的大小等。
(2)排序算法小结
1)若n较小(N<=50),则可以采用直接插入排序或简单选择排序。由于直接插入排序所需的记录移动操作较简单选择排序多,因而当记录本身信息量较大时,用简单选择排序较好。
2)若文件的初始状态已按关键字基本有序,则选用直接插入或冒泡排序为宜。
3)若n较大,则应采用时间复杂度为O(nlog2N)的排序方法:快速排序、堆排序或归并排序。
快速排序被认为是目前基于比较的内部排序中最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短。堆排序所需的辅助空间小于快速排序,并且不会出现快速排序可能出现的最坏情况,这两种排序都是不稳定的。
若要求排序稳定且时间复杂度为O(nlog2N),则可采用归并排序。但从单个记录起进行两两归并的排序算法并不值得提倡,通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件,然后再两两归并。直接插入排序是稳定的,因此改良后的归并排序仍是稳定的。
4)在基于比较的排序方法中,每次比较两个关键字的大小之后,仅仅出现两种可能的转移,因此可以用一棵二叉树来描述比较判定过程,由此可以证明:当文件的n个关键字随机分布时,任何借助于“比较”的排序算法,至少需要O(nlog2N)的时间。
5)若n很大,记录的关键字位数较少且可以分解时,采用基数排序较好。
6)当记录本身信号量较大时,为了避免消耗大量时间移动记录,可用链表作为存储结构。