7.11 内部排序总结

在已经研究的几种排序方法中,没有一种是最好的。有些方法适用于 nn 较小的情况,而另一些方法则适用于 nn 较大的情况。当输入序列部分有序时,插入排序可以很好的工作。且由于这种方法的额外空间开销较低,所以当 nn 较小时,这种方法是最好的排序方法。如果考察排序算法在最坏情况下的时间性能,归并排序是最好的,但归并排序比堆排序的空间开销更大,也比快速排序的空间开销稍大一些。如果考虑排序算法的平均时间性能,快速排序是最好的,但在最坏情况下其时间复杂度为 O(n2)O(n^2)。基数排序的时间性能取决于关键字的规模和基数的选取。

下表为快速排序、归并排序、堆排序和插入排序的平均运行时间,下图为平均运行时间的曲线图。

nn 快速排序 归并排序 堆排序 插入排序
0 0.041 0.027 0.034 0.032
10 1.064 1.524 1.482 0.775
20 2.343 3.700 3.680 2.253
30 3.700 5.587 6.153 4.430
40 5.085 7.800 8.815 7.275
50 6.542 9.892 11.583 10.892
60 7.987 11.947 14.427 15.013
70 9.587 15.893 17.427 20.000
80 11.167 18.217 20.517 25.450
90 12.633 20.417 23.717 31.767
100 14.275 22.950 26.775 38.325

7-9

results matching ""

    No results matching ""