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。