4

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

Collections课堂没有带来希望:

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

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

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

4

2 回答 2

2

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

于 2013-03-11T12:31:29.007 回答
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;

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

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

于 2013-03-11T12:32:06.480 回答