爲什麼Java的Arrays.sort方法爲不同類型使用兩種不同的排序算法？

Java的Arrays.sort方法使用快速排序基本類型數組和對象數組歸併排序。我相信大部分時間Quicksort比合並排序更快並且成本更低。我的實驗支持，儘管這兩種算法都是O（n log（n））。那麼爲什麼不同的算法用於不同類型？爲什麼Java的Arrays.sort方法爲不同類型使用兩種不同的排序算法？

來源

2010-09-14 zjffdu

+11

快速排序最壞的情況是N^2不是NlogN。 – codaddict 2010-09-14 08:27:25

等一下，如果你有一個'Integer'或者什麼的數組會發生什麼？ – 2010-09-14 08:30:28

這是不是解釋*在*你讀的來源？ – 2010-09-14 10:11:49

146

最可能的原因：快速排序不是穩定，即相同的條目可以在排序期間改變它們的相對位置;除此之外，這意味着如果您排序已經排序的數組，它可能不會保持不變。

由於原始類型沒有身份（有沒有辦法區分兩個整數使用相同的值），這沒有關係他們。但對於參考類型，它可能會導致某些應用程序出現問題。因此，這些使用穩定的合併排序。

OTOH，一個理由不使用（保證的n * log（n））的合併排序基本類型可能是它需要使陣列的克隆。對於引用類型，通常引用的對象比引用數組佔用的內存要多得多，這通常不重要。但對於原始類型，徹底克隆該陣列會使內存使用量翻番。

來源

2010-09-14 08:33:18

使用快速排序的另一個原因是，在平均情況下，快速排序比mergesort快。儘管快速排序比mergesort做的更多，但它的數組訪問更少。如果輸入包含很多重複的條目，在實際應用中並不罕見（我的猜測是雙樞軸快速排序也具有此屬性），3路快速排序也可以實現線性時間。 – 2016-02-14 06:53:31

一個原因，我能想到的是，快速排序爲O的最壞情況下的時間複雜度（N^2），而歸併保留的O最壞情況時間（的n logñ）。對於對象數組，有一個公平的期望，會有多個重複的對象引用，這是快速排序最差的一種情況。

有一個體面的visual comparison of various algorithms，特別注意最右邊的圖了不同的算法。

來源

2010-09-14 08:33:36 msw

今天在互聯網上我最喜歡的網站+1。 – 2010-09-14 09:52:53

java quicksort是一種修改過的快速排序，不會降低O（n^2），從文檔「此算法在許多數據集上提供n * log（n）性能，導致其他快速排序降級爲二次性能」 – sbridges 2012-01-07 17:46:29

「在許多數據集「不一樣」在所有「... – Puce 2013-03-01 10:22:32

我正在Coursera類的算法，並在講座鮑勃·塞奇威克教授提的Java系統排序評估的一個：

「如果程序員使用的對象，也許空間不是一個極爲重要審議並通過合併排序也許不是問題使用額外的空間。如果一個程序員使用原始類型，也許性能是最重要的事情，所以他們使用的快速排序。」

來源

2014-02-20 19:16:54 kukido

這不是主要原因。在這句話之後，有一個問題嵌入到視頻中，關於「爲什麼參考類型使用MergeSort？」（因爲它很穩定）。我認爲Sedgewick在視頻中沒有提到這個問題。 – likern 2015-07-26 17:48:07

根據this answer，Arrays#Sort()引爲對象陣列的Java 7 API文檔現在使用TimSort，這是歸併和插入排序的混合體。另一方面，原始數組的Arrays#sort()現在使用Dual-Pivot QuickSort。這些變化是在Java SE實現的開始7

來源

2015-05-08 05:48:26

Java的Arrays.sort方法使用快速排序，插入排序和歸併。甚至在OpenJDK代碼中都實現了單個和雙重數據透視快速排序。最快的排序算法取決於具體情況，獲勝者是：小數組的插入排序（目前選擇47個），大多數排序數組的mergesort，剩餘數組的快速排序，因此Java的Array.sort（）嘗試選擇最佳算法根據這些標準適用。

來源

2017-11-23 16:14:00

爲什麼Java的Arrays.sort方法爲不同類型使用兩種不同的排序算法？

回答

相關問題