Quicksort or O（N.logN）sort in jdk

Question

在jdk標準庫中是否有快速排序或另一種O（N.logN）排序，？

Collections類沒有帶來希望：

實現者應該可以隨意替代其他算法，只要本身是堅持規範。 （例如，通過排序所使用的算法不必是一個合併，但它必須是穩定的。）

和Collections.sort()沒有給出線索：

排序（表<ŧ > list） 根據元素的自然順序將指定列表按升序排序。

Answer 1

分選依賴於Arrays.sort。由於排序方法取決於類型，讀取JavaDoc並不那麼明顯。 一種改進的歸併排序，或者根據閾值的調整快速排序：

/** 
* Tuning parameter: list size at or below which insertion sort will be 
* used in preference to mergesort or quicksort. 
*/ 
private static final int INSERTIONSORT_THRESHOLD = 7; 

這裏是比較快速排序和歸併後：Quick Sort Vs Merge Sort

結論：信任的Java實現，除非你真的知道自己在做什麼。

Answer 2

Collections.sort是一種優化的合併排序，它實際上保證了每個情況下的O（n log n）並且它是穩定的; link。