java - Comparable/Comparator 使用的排序的内部工作

Question

这个问题已经有答案了:

How does the sort() method of the Collection class call the Comparable's compareTo()? (1 个回答)

已关闭 4 年前。

我正在研究用于 Java 中排序的 Comparable 和 Comparator 接口(interface)。我了解了它们的工作原理的基础知识。

我感兴趣的是它们的内部工作原理，即排序实际上是如何在内部进行的。

我假设compare/compareTo方法返回的正值、负值或零值将作为参数传递给另一个Sort方法。

我需要知道该排序方法的内部是什么或者正在使用哪种排序，任何文章或代码都会有帮助。

Answer 1

这取决于您调用哪种排序方法，但一般来说:它是故意不向用户公开的 Java 实现细节。

通过 Oracle Java 8，我可以看到基元排序使用了双枢轴快速排序、合并排序和插入排序的一些邪恶组合，具体取决于数组(算法中的任何点)是否 <386 个元素、<47 个元素元素和/或它是否确定它(启发式)“接近排序”。

另一方面，对象排序使用 Tim Peters 的 Python 排序算法，当算法中任意点的数组 <32 时，该算法使用 mini-Timsort，或者如果标志 java.util.Arrays，则使用 Mergesort。 useLegacyMergeSort 为 true。

[edit] 如果是对象数组，Arrays.sort 等于 Collections.sort。