jdk 标准库中是否有快速排序或其他 O(N.logN) 排序?
Collections
课堂没有带来希望:
只要遵守规范本身,实现者应该可以随意替换其他算法。(例如,sort 使用的算法不必是归并排序,但它必须是稳定的。)
并Collections.sort()
没有给出任何线索:
sort(List<T> list) 将指定列表按照其元素的自然顺序升序排序。
jdk 标准库中是否有快速排序或其他 O(N.logN) 排序?
Collections
课堂没有带来希望:
只要遵守规范本身,实现者应该可以随意替换其他算法。(例如,sort 使用的算法不必是归并排序,但它必须是稳定的。)
并Collections.sort()
没有给出任何线索:
sort(List<T> list) 将指定列表按照其元素的自然顺序升序排序。
Collections.sort
是一种优化的归并排序,它实际上在每种情况下都保证 O(n log n) 并且它是稳定的;链接。
排序依赖于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 实现。