Collections.Sort後續排序的性能？

Question

我正在使用Collections.sort自定義比較類。我聽說這有O(N log N)運行時複雜性。我很想知道當收集沒有改變時後續分類會發生什麼。

舉例來說，讓我說我有一個ArrayList Egg s，每個有一個大約size字段（我的比較排序）。如果我在數組列表中插入十個雞蛋並對其進行分類，我預計它會花費O(N log N)時間。

如果我再次排序，而不添加，刪除或更改任何元素，它仍然需要N log N時間？

Answer 1

我還沒有分析當前sun java庫中的代碼。但是，javadoc聲明使用合併排序。大多數合併排序在已排序的集合上產生O（n）性能。雖然這在文檔中沒有說明。我個人的經驗表明，在排序或近似排序的列表中，我的表現非常出色。

Answer 2

每個JavaDoc Collections.sort使用合併排序算法。

你可以看到它是如何做，爲自己，在這裏 - >http://www.sorting-algorithms.com/

Answer 3

的Javadoc說：「如果低子列表中的最高元素小於高子列表中的最低元素省略合併」。這似乎意味着什麼也沒有發生，所以它應該更快。

你可以隨時測試它。

Answer 4

爲了擴展EJP的答案，如果文檔指出合併過程是跳過的步驟，那麼在這種最好的情況下，運行時將是LG N，因爲它仍然會將列表分解爲LG N個子問題。與線性掃描相乘可以提高效率。