|
各种排序方法的比较 各种排序方法的选择 选择合适的排序方法应考虑的因素 ①待排序的记录数目n ②记录的大小（规模） ③关键字的结构及其初始状态 ④对稳定性的要求 ⑤语言工具的条件 ⑥存储结构 ⑦时间和辅助空间复杂度等 各种排序方法的选择 ①就平均时间性能而言快速排序最佳其所需时间最省但快速排序在最坏情况下的时间性能不如堆排序和归并排序当n较大时归并排序较堆排序省但归并排序所需的辅助空间最大 ②简单排序方法中直接插入排序最简单当待排序的结点已按键值基本有序且n较小时则应采用直接插入排序或冒泡排序直接插入排序比冒泡排序更快些因此经常将直接插入排序和其他的排序方法结合在一起使用 ③当n很大且键值位数较小时采用基数排序较好而当键值的最高位分布较均匀时可先按其最高位将待排序结点分成若干子表而后对各子表进行直接插入排序 ④从方法的稳定性来比较直接插入排序冒泡排序归并排序和基数排序是稳定的排序方法而直接选择排序希尔排序堆排序和快速排序都是不稳定的排序方法 |
