java - Collections.sort(...) 是如何工作的？

Question

为了清楚起见，我正在尝试找出 Collections.sort(list, new MyComp()) 方法如何以哪个顺序调用比较方法。

我有一个包含员工及其个人编号 (k) 的链表: 这些数字是: {1,2,3,4,5,6} MyComparator 中的 compare(Object o1, Object o2) 方法返回一些数字(与此问题无关)。 sort() 是如何调用比较方法的？ 它是否使用参数 1,2 然后 2,3 然后 3,4 然后 4,5 然后 5,6 调用它？我调试了它，但它跳回并比较 1,3 时出现了一些奇怪的序列。

它到底比较了什么？有什么规律吗？

Answer 1

进行的具体比较取决于 Collections.sort 方法在内部使用什么算法对元素进行排序。根据 Collections.sort 的 Javadoc:

The documentation for the polymorphic algorithms contained in this class generally includes a brief description of the implementation. Such descriptions should be regarded as implementation notes, rather than parts of the specification. Implementors should feel free to substitute other algorithms, so long as the specification itself is adhered to. (For example, the algorithm used by sort does not have to be a mergesort, but it does have to be stable.)

换句话说，Java 实现可以自由使用他们喜欢的任何排序算法，前提是它使相等的元素保持相同的相对顺序。这意味着如果不了解您的特定 Java 实现的更多信息，就无法知道将要进行哪些比较。 (如果我没记错的话，Java 的 Oracle 版本实际上将其 Collections.sort 的实现从 Java 7 切换到了 Java 8，尽管我可能弄错了。)

也就是说，这不是一件坏事。编写比较器背后的想法是告诉排序方法“做任何你需要做的事情来排序，如果你需要进行比较，这里就是这样做的方法。”这是一个很好的抽象 - 你说出如何对事物进行排序，然后神奇的排序黑匣子就会去使用它来让事物井井有条。