何時使用哪種排序算法，什麼時候不應該使用

Question

我們看到很多排序技術，如合併，快速，堆。你能幫我決定在哪種環境中使用哪種排序技術（如問題中）？我們應該何時使用這些排序算法中的哪一個，哪些不是（它們在時間和空間上的缺點）？

我期待答案的東西以這種形式： 一）我們將使用合併排序的時候......我們絕對不應該使用合併排序時... b）我們將使用快速排序的時候......我們應該絕對不使用快速排序時...

Answer 1

有跡象表明，表徵每個排序算法的行爲的一些基本參數：

• 平均情況計算複雜
• 最壞的情況下計算的複雜性
• 內存需求
• 穩定性（即它是一個stable sort？）

所有這些都是widely documented for all commonly used sorts，這是您需要提供所需格式答案的所有信息。然而，由於每種類型的四個參數都會考慮很多事情 - 並非所有這些都是相關的 - 要考慮，嘗試給出這樣的「腳本化」答案並不是一個好主意。此外，還有更高級的概念可以考慮（比如在幾乎排序或反向排序的數據上運行時的行爲，緩存性能，對惡意構建的輸入的抵制），使得這樣的答案更加冗長和容易出錯。

我建議你花一些時間熟悉上面提到的四個基本概念，或許通過visualizing how each type of sort works簡單輸入並閱讀排序算法的介紹性文字。做到這一點，很快你就可以自己回答這些問題。

Answer 2

對於初學者來說，看看這個comparison table在維基百科上，比較標準會給你線索尋找什麼算法及其可能的折衷。