排序在最壞情況下O（n * log（n））

Question

是否有一種工作在O（n * log（n））最壞情況時間複雜度的數組？

我在維基百科看到有類似的，但它們是unstable，這是什麼意思？有沒有辦法在低空間複雜性？

是否有最佳排序算法？

Answer 1

只需要O（1）額外內存（因此允許修改輸入數組）的算法通常被描述爲「in-place」，並且這是最低的空間複雜度。

根據當輸入中有兩個元素時，將排序描述爲「穩定」或不是，其中比較等同，但在某種程度上是可區分的。例如，假設您有一堆帶有整數字段和字符串字段的記錄，並將它們排序在整數字段上。問題是，如果兩個記錄具有相同的整數值但字符串值不同，那麼輸入中第一個記錄的輸出中的第一個也會先出現在輸出中，還是有可能會顛倒？穩定的排序是保證比較相同但不相同的元素順序的排序。

這是很難做出比較排序是就地，和穩定，和達到O(n log n)最壞情況下的時間複雜度。我有一個模糊的想法，不知道它是否可能，但我沒有及時更新它。

上次有人問這個話題，我發現一對夫婦的相關論文，但這個問題並不等同於這樣一個問題：

How to sort in-place using the merge sort algorithm?

至於「最佳」之類的關注 - 一些排序策略利用了這樣一個事實，即總體來說，通過大量的應用程序，計算機花費大量的時間對未被隨機洗牌的數據進行排序，它具有一定的結構。 Timsort是一種利用通常遇到的結構的算法。它在很多實際應用中表現非常好。你不能把它描述成「最好」的類型，因爲它是一種似乎在實踐中表現良好的啓發式方法，而不是對先前算法的嚴格改進。但是，將它作爲默認排序的人（Python，Java 7，Android）認爲它是「最好的」。您可能不會將其描述爲「低空間複雜度」，但它並不比標準的合併排序更好。

Answer 2

你可以檢查mergesort，quicksort或heapsort之間的所有很好描述here。

還有基數排序，其複雜度是O（kN），但它充分利用了額外的內存消耗。

您還可以see，對於較小的集快速排序是速度較快，但隨後歸併牽頭，但所有的這情況下專用的，所以把你的時間來研究所有4種算法

Answer 3

對於這個問題最好算法中，簡單的答案是，這取決於。它取決於設置要進行排序，這取決於你的requirement.Say的數據的大小，冒泡排序有最壞情況和平均複雜度都О（N ） ，其中n是正在排序的項目的數量。存在許多排序算法，具有明顯更好的O（n log n）的最壞情況或平均複雜度。甚至其他的排序算法（例如插入排序）的其他排序算法傾向於具有比氣泡排序更好的性能。因此，當n很大時，冒泡排序不是一種實用的排序算法。

在簡單平均情況Θ（N ）算法，選擇排序幾乎總是優於冒泡排序，但一般是由插入排序勝過。

選擇排序大大上較大的陣列由Θ優於作爲歸併例如（N log n）的分而治之算法。但是，插入排序或選擇排序對於小型陣列通常都更快。

同樣，您可以根據自己的要求自己選擇最佳排序算法。

Answer 4

已證實O（n log n）是排序通用項目的下界。也證明了O（n）是排序整數的下界（至少需要讀取輸入:)）。

問題的具體實例將決定什麼是最適合您需求的算法，即。排序1M字符串與在2MB RAM中排序2M 7位整數不同。

另外考慮到除了漸近的運行時複雜性之外，實現還有很多不同，以及可用內存和緩存策略的數量。我可以在python的1行中實現快速排序，大致保持O（n log n）的複雜性（對於關鍵點有一些警告），但是Big-Oh表示法並沒有提到與常量項相關的內容，這也是相關的。這是30倍〜比Python慢​​內置的排序，這很可能是用C語言編寫的BTW）：

qsort = lambda a: [] if not a else qsort(filter(lambda x: x<a[len(a)/2], a)) + filter(lambda x: x == a[len(a)/2], a) + qsort(filter(lambda x: x>a[len(a)/2], a)) 

對於有關穩定/不穩定分類討論，請看這裏http://www.developerfusion.com/article/3824/a-guide-to-sorting/6/。

你可能想要一本好的算法書（即Cormen或Skiena）。

Answer 5

• Heapsort，也許randomized quicksort
• stable sort
• 爲他人已經提到：沒有沒有。例如，你可能想要並行化你的排序算法。這導致了完全不同的排序算法..

Answer 6

關於你的問題意味着穩定，讓我們考慮以下因素：我們有一類與年齡相關的兒童：

Phil, 10 
Hans, 10 
Eva, 9 
Anna, 9 
Emil, 8 
Jonas, 10 

現在，我們要排序的兒童按年齡遞增（沒有別的）。然後，我們看到菲爾，漢斯和喬納斯都已經有10歲了，所以我們不清楚我們要點什麼順序，因爲我們只按年齡排序。

現在來穩定：如果我們排序穩定我們排序菲爾，漢斯和喬納斯在他們以前的順序，即我們把菲爾先，然後漢斯，最後，喬納斯（只是因爲他們在這個順序在原始序列中，我們只考慮年齡作爲比較標準）。同樣的，我們必須在安娜之前把伊娃（都是同一個年齡段，但是伊娃在安娜之前的原始序列）。

所以，其結果是：

Emil, 8 
Eva, 9 
Anna, 9 
Phil, 10 \ 
Hans, 10 | all aged 10, and left in original order. 
Jonas, 10/

爲了把它在一個概括地說：穩定性意味着，如果兩個元素是相等的（WRT所選擇的排序標準），所述一個來首先在原始序列在結果序列中仍然排在第一位。

注意，您可以輕鬆地將任何排序算法到一個穩定的排序算法：如果您原來的序列持有n元素：e1, e2, e3, ..., en，您只需連接一個計數器每個：(e1, 0), (e2, 1), (e3, 2), ..., (en, n-1)。這意味着您爲每個元素存儲其原始位置。

如果現在兩個元素相等，您只需比較它們的計數器並首先將計數器值較低的那個計數器。這增加了運行時（和內存）O(n)，這是漸近沒有惡化，因爲最佳（比較）排序算法需要已經O(n lg n)。