爲什麼快速排序被認爲是最快的排序算法？

-3

快速排序的最壞情況下的時間複雜度爲O（n^2），而其他像堆排序和合並排序具有最壞情況下的時間複雜度，因爲O（n log n）.still快速排序被認爲更快...爲什麼？爲什麼快速排序被認爲是最快的排序算法？

2015-09-06 Himanshu

請看[this]（http://cs.stackexchange.com/questions/3/why-is-quicksort-better-than-other-sorting-algorithms-in-practice） – Sait

我可以知道原因..爲什麼我的問題被拒絕投票，以便將來我會照顧這個問題？ – Himanshu

是的。我猜這是因爲（1）這個問題太廣泛了（2）你沒有展示任何你已經完成的工作（例如，使用Google搜索同一個問題並閱讀網頁，在閱讀之後詢問更具體的問題更多信息，或者編寫一段代碼並分析不同場景下的不同排序算法，然後詢問有關代碼的問題等）。另請閱讀[how-to-ask]（http://stackoverflow.com/help /如何對問）。 – Sait

在附註上，如果對整數數組進行排序，則計數/基數排序是最快的。

一般來說，合併排序可以做更多的動作，但比快速排序少。合併排序的典型實現使用與原始數組大小相同的臨時數組，或1/2大小（將第二部分排序到第二部分，將第一部分排序到臨時數組中，將臨時數組+第二部分合併到原始數組中），所以它需要比快速排序更多的空間，最好只需要log2（n）級別的嵌套，並且爲了避免最壞情況嵌套，可以使用嵌套檢查並將快速排序改變爲堆排序（這稱爲內插）。

如果比較開銷大於移動開銷，則合併排序更快。比較花費的時間比移動更常見的例子是將指向數組的指針排序。只有（4或8字節）指針纔會移動，而字符串可能會更大（對於大量字符串也是如此）。

如果要排序的數據有重要的預先排序，那麼timsort（固定大小運行）或「自然」合併排序（可變大小運行）將會更快。

來源

2015-09-06 23:38:30 rcgldr

雖然這是事實，快速排序有爲O（n^2），只要快速排序執行正常隨機化輸入，其平均情況（預期）運行時間的最壞情況下的時間複雜度爲O（n日誌n）。

此外，與其他流行選擇（如合併排序）相比，由漸進表示法隱藏的常量因子在實踐中很重要。因此，根據預期，快速排序將勝過其他O（n日誌n）比較排序，儘管不太可口的最壞情況邊界

來源

2015-09-06 23:16:12 lemonhead

不完全如此。 Quicksort在大多數情況下是最好的，但它的時間複雜度可能是O（n^2），但並不意味着它總是這樣。問題在於選擇正確的關鍵點，如果您選擇正確，則您的時間複雜度爲O（n log n）。另外，quicksort是實現中最便宜/最容易的之一。

來源

2015-09-06 23:16:57 Kraxi

爲什麼快速排序被認爲是最快的排序算法？

回答

相關問題