|
|
|
|
|
|
|
|
|
|
|
综合比较以上所讨论的各种排序方法，大致结果如下表所示。
|
|
|
|
|
|
|
|
不同的排序方法各有优缺点，可根据需要运用到不同的场合。选取排序方法时需要考虑的主要因素有：待排序的记录个数n，记录本身的大小，关键字的分布情况，对排序稳定性的要求，语言工具的条件，辅助空间的大小等。
|
|
|
|
|
|
（1）若待排序的记录数目n较小时，可采用插入排序和简单选择排序。由于直接插入排序所需的记录移动操作较简单选择排序多，因此当记录本身信息量较大时，用简单选择排序方法较好。
|
|
|
|
（2）若待排序记录按关键字基本有序，则宜采用直接插入排序或冒泡排序。
|
|
|
|
（3）若n较大，则应采用时间复杂度为O（nlog2n）的排序方法，例如快速排序、堆排序或归并排序。
|
|
|
|
快速排序在目前内部排序方法中被认为是最好的方法，当待排序的关键字随机分布时，快速排序的平均时间最短；堆排序只需一个辅助存储空间，并且不会出现在快速排序中可能出现的最坏情况。这两种排序方法都是不稳定的排序方法，若要求排序稳定，可选择归并排序。通常可将归并排序和直接插入排序结合起来使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并。
|
|
|
|
前面讨论的内部排序算法都是在一维数组上实现的。当记录本身信息量较大时，为避免耗费大量的时间移动记录，可以采用链表作为存储结构。
|
|
|
