各種排序算法的比較

各種排序算法的比較

1.穩定性比較

插入排序、冒泡排序、二叉樹排序、二路歸并排序及其他線形排序是穩定的

選擇排序、希爾排序、快速排序、堆排序是不穩定的

2.時間複雜性比較

插入排序、冒泡排序、選擇排序的時間複雜性為O(n2)

其它非線形排序的時間複雜性為O(nlog2n)

線形排序的時間複雜性為O(n);

3.輔助空間的比較

線形排序、二路歸并排序的輔助空間為O(n),其它排序的輔助空間為O(1);

4.其它比較

插入、冒泡排序的速度較慢，但參加排序的序列局部或整體有序時，這種排序能達到較快的速度。

反而在這種情況下，快速排序反而慢了。

當n較小時，對穩定性不作要求時宜用選擇排序，對穩定性有要求時宜用插入或冒泡排序。

若待排序的記錄的關鍵字在一個明顯有限範圍内時,且空間允許是用桶排序。

當n較大時，關鍵字元素比較随機，對穩定性沒要求宜用快速排序。

當n較大時，關鍵字元素可能出現本身是有序的，對穩定性有要求時，空間允許的情況下。

宜用歸并排序。

當n較大時，關鍵字元素可能出現本身是有序的，對穩定性沒有要求時宜用堆排序。

*************************************************************************************

重溫經典排序思想--C語言常用排序全解