爲什麼合併排序用於Android/Java API中的對象？

Question

對於原始類型的Java Arrays.sort()使用快速排序。另一方面Arrays.sort()爲對象使用合併排序。而且，Collection.sort()也使用合併排序。集合排序使用Arrays排序下面的實現。所以，簡單地說，我可以說基元使用快速排序進行排序，但對象使用合併排序進行排序。

我的猜測是它與自己排序算法有關。關於「快速排序」和「合併排序」的SO有很多討論，如this和this。似乎有一個矛盾的主張，哪一個更好，這是可以理解的，因爲這取決於數據集。

我的理解是

• 到位：快速排序獲勝。合併排序可以在鏈接列表中就地實現
• 外部存儲數據：合併排序勝出。
• 排序列表（由任何形式的鏈接列表支持）：合併排序勝出。 Link

Android API似乎遵循與Java相同的模式。這是我在Arrays.java

public static void sort(long[] array) { 
    DualPivotQuicksort.sort(array); 
} 

而這個發現，

public static void sort(Object[] array) { 
    ComparableTimSort.sort(array); 
} 

什麼，我不明白的是，是什麼使合併排序一個很好的候選人進行排序在Java或Android中的對象？爲什麼不把這個決定留給開發者？

Answer 1

關鍵問題是排序穩定性 - 如果從排序順序的角度來看兩個元素是相同的，它們是否以與輸入中相同的順序顯示在結果中。

它對於例如， long。輸入中的所有3實例將組合在一起，並且沒有人在意哪個是哪個實例。

另一方面，對象可能在不影響排序順序的方面有所不同。如果您按腿數排​​序動物，則可能會在乎「貓」和「狗」是否保持原始順序。

Arrays.sort mergesort是穩定的。用於基元的快速排序不需要穩定。

Answer 2

歸併排序是穩定的：等於元素將無法重新排序作爲排序的結果

Answer 3

請參閱這樣的回答：Why Collections.sort uses merge sort instead of quicksort?

TL; DR：

快速排序有兩個重大缺陷當與mergesort比較時：

1. 它不穩定（如parsifal指出的）。
2. 它不保證n log n性能;它可以降解爲病理輸入的二次表現。

Answer 4

我覺得

的問題是什麼讓歸併排序一個很好的候選人進行排序Java對象和 快速排序，對原語？

已經被人回答了，但

的問題，爲什麼這個決定還沒有被留下來開發？

尚未解決。

事實是，任何開發人員可以很容易地從Collection或ArrayList和隱藏的sort()方法派生一個新類（因爲sort()是static方法必須是hidden, not overidden），並使用自己的自定義實現它。

這很少（如果有的話）完成的事實也許是因爲今天的大多數年輕程序員比C++更多地接觸Java。在Java社區中，「抽象」意味着你不知道一個類的底層實現是如何工作的，而且你並不需要。 JVM的機器獨立性使得我們對速度/效率權衡的直覺變得遲鈍。因此，我們中的很多人對於數據結構和算法的理解並不像一些較老的和更有經驗的程序員那樣清晰。

這幾乎與C++中對抽象的理解相反。引用Alex Stepanov：

事實上，我不相信一個庫可以消除程序員需要知道算法和數據結構的需求。它僅僅消除了程序員實現它們的需要。需要 來理解數據結構的基本屬性，以便正確使用它們，以便應用程序滿足其自身複雜性 的要求。