timsort和quicksort之間的比較

爲什麼當timsort（根據維基百科）似乎表現更好時，我主要聽說quicksort是最快的整體排序算法？谷歌似乎沒有任何比較。timsort和quicksort之間的比較

2011-10-14 chenglou

有了更多的想法和一些參考，這可能是一個很好的問題。 –

+19

因爲人們選擇忽略快速排序是O（n^2）最差的情況。 – Patrick87

一個可能的答案是：你對錯誤的人說話。但正如其他答案已經暗示的那樣：qsort要陳舊得多，所以它在更多的庫中使用 - 而且您知道：切勿觸摸正在運行的系統。如果平均運行時間（意味着：在使用它的人的使用情況下）並不比其他算法的運行時間（如timsort）差得多，那麼人們就太懶惰了（或者有更好的事情要做）有些事情，在同一時間也是這樣。在某些應用程序中（例如python），timsort已經是默認的了。 – flolo

TimSort是高度優化的mergesort，它比舊的mergesort更穩定更快。

與快速排序比較時，它有兩個優點：

這是令人難以置信的速度近排序的數據序列（包括反向排序的數據）;
最壞的情況仍然是O（N * LOG（N））。

說實話，我不認爲＃1是一個優勢，但它確實給我留下了深刻的印象。

這裏是快速排序的優勢

快速排序是非常非常簡單，即使是高度優化的實現，我們可以在20行寫下了pseduo代碼;
QuickSort在大多數情況下是最快的;
內存消耗是LOG（N）。

目前，Java 7 SDK實現timsort和一個新的快速排序的變體：即雙樞軸快速排序。

如果您需要穩定排序，請嘗試timsort，否則以quicksort開始。

來源

2013-10-25 10:25:14 Chang

＃1 *可以是一個巨大的優勢。如果您維護一個必須經常重新排序的數據列表（因爲項目被插入，附加或修改），使用一種算法可以非常便宜地重新排序該數據非常有用。它是否有用取決於具體情況，當然，但在某些情況下它很大，而且也很明顯：幾乎排序的列表不應該難以分類。 –

@JeremyWest：如果您知道數據已經排序，您應該使用二進制搜索來插入新值。不要一遍又一遍地排序。 –

@EricDuminil二進制搜索很快，但在數組中間插入不是。有許多應用程序最簡單（通常是最有效的）解決方案是在需要對其進行排序時重新排序主要排序的列表，但要使其排序不然。或者你閱讀大部分已排序的數據，然後需要對其進行排序的情況。我並不是說這是*總是最好的解決方案，但有時候是這樣。這也是爲什麼排序在主要排序列表上表現良好的原因之一，尤其是對於標準庫。 –

或多或少，它與Timsort是混合排序算法有關。這意味着雖然它使用的兩種基本排序（合併排序和插入排序）對於多種數據都比Quicksort差，但Timsort僅在有利時才使用它們。

在稍深的級別上，如Patrick87所述，quicksort是最壞情況的O（n ）算法。選擇一個好的關鍵不是hard，但保證O（n log n）快速排序的代價是平均排序通常較慢。

有關Timsort的更多詳細信息，請參見this answer以及鏈接的博客文章。它基本上假定大部分數據已經部分排序，並構造了排序數據的「運行」，允許使用mergesort進行高效合併。

來源

2011-10-14 16:13:23 brc

一般來說quicksort是基本數組的最佳算法。這是由於內存局部性和緩存。

JDK7使用TimSort for Object數組。對象數組只保存對象引用。該對象本身存儲在Heap中。爲了比較對象，我們需要從堆中讀取對象。這就像從堆的一部分讀取一個對象，然後從堆的另一部分隨機讀取對象。會有很多緩存未命中。我猜這是因爲內存局部性不再重要。這可能是爲什麼JDK只使用TimSort for Object數組而不使用基本數組。

這只是我的猜測。

來源

2014-11-17 02:01:40

這裏是我的機器的基準數字（i7-6700 CPU，3.4GHz，Ubuntu 16.04，gcc 5.4。0，參數：SIZE = 100000，運行= 3）：

$ ./demo 
Running tests 
stdlib qsort time:     12246.33 us per iteration 
##quick sort time:     5822.00 us per iteration 
merge sort time:     8244.33 us per iteration 
...  
##tim sort time:     7695.33 us per iteration 
in-place merge sort time:   6788.00 us per iteration  
sqrt sort time:      7289.33 us per iteration  
... 
grail sort dyn buffer sort time: 7856.67 us per iteration

基準來自斯文森的sort項目中，他爲C. 想必實施了幾個排序算法，他的實現是不夠好，具有代表性，但我沒有調查過他們。

所以你真的不知道。基準數字只在最多兩年內保持相關性，然後您必須重複它們。可能，當問題被問到時，timsort在2011年擊敗了qsort waaay，但時代已經改變。或qsort總是最快，但timsort擊敗它非隨機數據。或者Swenson的代碼不太好，一個更好的程序員會在timsort的幫助下扭轉局面。或者，也許我在編譯代碼的時候並沒有使用正確的CFLAGS。或者...你明白了。

來源

2017-09-24 20:45:36

timsort和quicksort之間的比較

回答

相關問題