sorting - jdk 中的快速排序或 O(N.logN) 排序

Question

jdk 标准库中是否有快速排序或其他 O(N.logN) 排序？

Collections课堂没有带来希望：

只要遵守规范本身，实现者应该可以随意替换其他算法。（例如，sort 使用的算法不必是归并排序，但它必须是稳定的。）

并Collections.sort()没有给出任何线索：

sort(List<T> list) 将指定列表按照其元素的自然顺序升序排序。

Answer 1

Collections.sort是一种优化的归并排序，它实际上在每种情况下都保证 O(n log n) 并且它是稳定的；链接。

Answer 2

排序依赖于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;

这是一个比较快速排序和合并排序的帖子：快速排序与合并排序

结论：除非您真的知道自己在做什么，否则请相信 Java 实现。