浙江大學-數據結構-演算法排序的比較-10.4.1

來自專欄 Excalibur4 人贊了文章

排序演算法的比較

那我們前面說過了沒有任何一種排序演算法，是任何情況下都最好的，所以我們前面講了這麼多排序的演算法，最後就給大家總結一下，比較一下我們學過的所有演算法，它們各自的優缺點。

前面3種呢，我們統稱簡單排序，都是最直接了當，最簡單的排序方法，那麼我們可以看到它們的時間複雜度都是比較差的，當然它們共同的優點都是程序非常好寫，寫起來非常短，都不需要額外的空間，冒泡排序和直接插入排序因為它們每次交換的都是相鄰的元素，所以是慢的，但是好處呢，是不需要交換的時候就不交換，那麼它們這兩種演算法都是穩定的，簡單選擇排序呢，它是跳著交換的，跳著交換導致的結果就是這個演算法有可能是不穩定的，那希爾排序最先打破N^2這個下界的演算法，它的複雜度是N^d，這個d實際上取決於增量序列的選擇，我們知道希爾排序的好壞是很大程度上依賴於增量序列的選擇，你如果增量序列選的好，這個d呢會是小於2的，最壞情況下呢，這個d就是等於2，所以最壞情況下這有就是N^2,那麼因為它是跳著排的，所以它也是不穩定的，那堆排序和歸併排序這兩個排序從理論上講，它們的時間複雜度都是最好的，無論如何都是NlogN,歸併排序的缺點呢，它是需要一個額外的空間，當你要排的數據量非常大的時候，歸併排序就會導致你只能排一半的數據了，本來你可以排下的數據，因為這個空間的問題，導致你排不下，只是歸併排序很大的問題，當然它的好處是它是穩定的，堆排序理論上看很美，但是實際的效果，雖然它是NlogN,但是O這個常數會比較大，所以它到底跟快速排序哪個快呢？大家可以自己去做一個試驗，比較一下，看看什麼情況下到底那種演算法快，堆排序和快速排序的缺點都是不穩定的演算法，那麼快排呢，說起來你總可以構造一種最壞的情況使得它的時間複雜度是N^2這個數量級的，而且因為它是遞歸的，所以它需要額外的空間，這是在時間複雜度最好的情況下，它的空間複雜度也需要O(logN),為什麼是這樣?自己去分析一下2333，平均時間複雜度是很好的，NlogN,而且關鍵是這個前面的常數比較小，所以在實際應用中快速排序是非常快的，那基數排序呢，在某種情況下，它會打破NlogN這個魔咒，它會比NlogN還要快，它快到近乎線性，當然這就取決於你到底需要多少個桶，你需要多少趟的分配和收集，那它的額外空間複雜度也是至少需要建立這麼多個桶，然後在每一個桶裡頭它得留這麼大的空間，給它放進去，所以到底什麼情況下合算，這個要看情況，當然好處也是，如果你實現正確的話，基數排序也是穩定的，需要搞清楚在哪種情況下用哪種演算法最合算。