1.從時間復雜度比較?
　　從平均時間復雜度來考慮，直接插入排序、冒泡排序、直接選擇排序是三種簡單的排序方法，時間復雜度都為O(n2)，而快速排序、堆排序、二路歸并排序的時間復雜度都為O(nlog2n)，希爾排序的復雜度介于這兩者之間。若從最好的時間復雜度考慮，則直接插入排序和冒泡排序的時間復雜度最好，為O(n)，其它的最好情形同平均情形相同。若從最壞的時間復雜度考慮，則快速排序的為O(n2)，直接插入排序、冒泡排序、希爾排序同平均情形相同，但系數(shù)大約增加一倍，所以運行速度將降低一半，最壞情形對直接選擇排序、堆排序和歸并排序影響不大.
2．從空間復雜度比較?
　　歸并排序的空間復雜度最大，為O(n)，快速排序的空間復雜度為O(log2n)，其它排序的空間復雜度為O（1）。?
3.從穩(wěn)定性比較?
　　直接插入排序、冒泡排序、歸并排序是穩(wěn)定的排序方法，而直接選擇排序、希爾排序、快速排序、堆排序是不穩(wěn)定的排序方法。?
4．從算法簡單性比較?
　　直接插入排序、冒泡排序、直接選擇排序都是簡單的排序方法，算法簡單，易于理解，而希爾排序、快速排序、堆排序、歸并排序都是改進型的排序方法，算法比簡單排序要復雜得多，也難于理解。

　　迄今為止，已有的排序方法遠遠不止本章討論的這些方法，人們之所以熱衷于研究多種排序方法，不僅是由于排序在計算機中所處的重要地位，而且還因為不同的方法各有其優(yōu)缺點，可適用于不同的場合。選取排序方法時需要考慮的因素有：
待排序的記錄數(shù)目n；記錄本身信息量的大小；關鍵字的結(jié)構(gòu)及分布情況；對排序穩(wěn)定性的要求；語言工具的條件，輔助表的大小等。依據(jù)這些因素，可得出如下幾點結(jié)論：
（1）若n較小（譬如n50)，可采用直接插入排序或直接選。由于直接插入排序所需記錄移動操作較直接選擇排序多，因此若記錄本身信息量較大時，則選用直接選擇排序為宜。?
（2）若文件的初始狀態(tài)已是按關鍵字基本有序，則選用直接插入排序泡排序為宜。?
（3）若N較大，則應根據(jù)其時間復雜度來選擇排序方法：快速排序\堆排序或歸并排序，快速排序是目前基于內(nèi)部排序的中被認為是最好的方法，檔待排序的關鍵字是隨機時，快速排序的平均時間最少，但堆排序所需的輔助空間少于快速排序，并且不會出現(xiàn)序可能出現(xiàn)的最壞情況，這兩種排序方法都是不穩(wěn)定的，若要求排序穩(wěn)定則可選用歸并排序。但本文章結(jié)合介紹的兩兩歸并排算法并不值得提倡，通常可以將它和直接排序結(jié)合在一起用。先利用直接插入排序求得的子文件，然后再兩兩歸并之。因為直接插入排序是穩(wěn)定的，所以，改進后的歸并排序是穩(wěn)定的。
（4）前面討論的排序算法，除排序外，都是在一維數(shù)組上實現(xiàn)的，當記錄本身信息量較大時，為了避免浪費大量時間移動記錄，可以用鏈表作為存儲結(jié)構(gòu)，如插入排序和歸并排序都易于在鏈表上實現(xiàn)，并分別稱之為表和歸并表，但有的方法，如快速排序和堆排序，在鏈表上難于實現(xiàn)，在這種情況下，可以提取關鍵字建立索引表，然后，對索引表進行排序。然而更為簡單的方法是;引入一個整形向量作為輔助表，排序前，若排序算法中要求交換，則只需交換R[I]和R[j]即可，排序結(jié)束后，向量就指示了記錄之間的順序關系.

轉(zhuǎn)載于:https://www.cnblogs.com/sheropan/p/5022437.html

總結(jié)

以上是生活随笔為你收集整理的数据结构——各排序算法的比较的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。