Java排序函數

在java中，collections.sort使用合併排序算法而不是快速排序。但Arrays.sort使用快速排序。（我不確定上述事實，但我發現在互聯網上就像在網站上，如CodeRanch，如果他們不使用該算法，請告訴我）Java排序函數

現在我知道這兩種算法的平均複雜度是相同的。唯一的事實是快速排序最差的是O（n^2），但這並不常見。而且我們不關心當今世界的空間，所以合併排序不是就地算法並不重要。但是我們關心穩定性，所以我們爲什麼使用array.sort的快速排序，因爲它不是一個穩定的算法。是因爲它只關心整數，但我不認爲這是一個很好的理由。

來源

2015-04-22 Arjun Chaudhary

我以爲他們都使用TimSort。我需要檢查源代碼。 –

哦，你確定我在網上找到了。 –

@ArjunChaudhary「我發現在互聯網上」是相當無益的。你在哪找到它的？ – dimo414

您可以通過查看相關的Javadocs甚至source code輕鬆驗證您的前提。首先，注意Collections.sort(List<T>)簡單地委託給Arrays.sort(Object[])（source）：

public static <T extends Comparable<? super T>> void sort(List<T> list) { 
    Object[] a = list.toArray(); 
    Arrays.sort(a); 
    ListIterator<T> i = list.listIterator(); 
    for (int j=0; j<a.length; j++) { 
     i.next(); 
     i.set((T)a[j]); 
    } 
}

所以這兩種方法都會有相同的行爲和運行。正如文檔中指出的那樣，實現是TimSort，一個合併排序和插入排序混合。它保證穩定。因此，無論您有數組還是集合，排序對象的工作方式都是相同的。

你鏈接到的文章指的是排序基元數組。關於原始數組需要做的假設較少，特別是相同的原始數據根據定義是不可區分的。這意味着沒有必要確保穩定的排序。您會注意到原始排序方法的文檔，如Arrays.sort(int[])，並沒有提到這些排序方法的穩定性，因爲這樣的細節沒有意義。排序數據可以相同但不相同時，穩定性只是很重要。

來源

2015-04-22 00:46:38 dimo414

Arrays.sort將比Collections.sort稍快，因爲Collections.sort在內部調用Arrays.sort。當處理基元時，穩定性不相關，因爲具有相同值的基元可以重新排列而沒有副作用。 Arrays.sort提供了額外的性能優勢。因此，對於原始數組，Arrays.sort將是首選。

來源

2015-04-22 00:31:13 Aswin

這並不回答這個問題。 – hexafraction

是的，這實際上是關於他們使用哪種算法，爲什麼？ –

Arrays.sort並沒有真正使用常見的快速排序實現，javadoc中指定：

的排序算法是一個雙樞軸快速排序弗拉基米爾· Yaroslavskiy，喬恩·本特利，以及約書亞·布洛克。該算法在許多數據集上提供了 O（n log（n））性能，這些數據集導致其他快速排序降級爲二次性能，並且通常比傳統（單軸）Quicksort實現更快。

看看位於DualPivotQuicksort的排序算法;正如您在註釋中看到的，根據給定的數組使用不同的排序算法。

至於Collections排序方法，它在接收到的實現上調用sort（在我驗證的情況下）代表Arrays.sort。

來源

2015-04-22 00:33:07

Arrays.sort僅對原始數組使用雙樞軸快速排序算法，其中穩定排序算法和不穩定排序算法之間沒有區別。這通常被認爲稍快，但不穩定，所以它只用於穩定性無關的情況。

Arrays.sort對象數組，和Collections.sort，使用Timsort，這是一個合併排序變體，進行穩定的排序。

來源

2015-04-22 00:38:21

回答

相關問題