知乎上有一個問題是這樣的：
堆排序是漸進最優的比較排序演算法，達到了O(nlgn)這一下界，而快排有一定的可能性會產生最壞劃分，時間復雜度可能為O(n^2)，那為什么快排在實際使用中通常優于堆排序？
昨天剛好寫了一篇關于快排優化的文章，今天再多做一個比較吧，首先先看一個排序演算法圖：
| 排序方法 | 平均情況 | 最好情況 | 最壞情況 | 輔助空間 | 穩定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | 穩定 |
| 簡單選擇排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 穩定 |
| 直接插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | 穩定 |
| 希爾排序 | O(nlogn)~O(n^2) | O(n^1.3) | O(n^2) | O(1) | 不穩定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不穩定 |
| 歸并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 穩定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn)~O(n) | 不穩定 |
可以看到，到達nlogn級別的排序演算法，一共有三種，分別是堆排序，歸并排序以及快速排序，其中只有歸并排序最穩定，那么，為什么要說快速排序的平均情況是最快的呢？
實際上在演算法分析中，大O的作用是給出一個規模的下界，而不是增長數量的下界，因此，演算法復雜度一樣只是說明隨著資料量的增加，演算法時間代價增長的趨勢相同，并不是執行的時間就一樣，這里面有很多常量引數的差別，比如在公式里各個排序演算法的前面都省略了一個c，這個c對于堆排序來說是100，可能對于快速排序來說就是10，但因為是常數級所以不影響大O，
另外，即使是同樣的演算法，不同的人寫的代碼，不同的應用場景下執行時間也可能差別很大，下面是一個測驗資料：
測驗的平均排序時間：資料是隨機整數，時間單位是s
資料規模 快速排序 歸并排序 希爾排序 堆排序
1000萬 0.75 1.22 1.77 3.57
5000萬 3.78 6.29 9.48 26.54
1億 7.65 13.06 18.79 61.31
堆排序每次取一個最大值和堆底部的資料交換，重新篩選堆，把堆頂的X調整到位，有很大可能是依舊調整到堆的底部（堆的底部X顯然是比較小的數，才會在底部），然后再次和堆頂最大值交換，再調整下來，可以說堆排序做了許多無用功，
總結起來就是，快排的最壞時間雖然復雜度高，但是在統計意義上，這種資料出現的概率極小，而堆排序程序里的交換跟快排程序里的交換雖然都是常量時間，但是常量時間差很多，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/65006.html
標籤：C
上一篇：計算周幾的程式(基姆拉爾森公式)
下一篇：【漫畫】什么是外部排序？【轉】