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

Question

要清楚的是，我正在试图了解Collections.sort(list, new MyComp())方法如何调用compare方法的顺序。

我有一个LinkedList，其中包含员工及其个人编号（k）： 这些数字是： {1,2,3,4,5,6} MyComparator中的compare(Object o1, Object o2)方法返回一些数字（与此有关系）。 sort()如何调用compare方法？ 它会先调用参数1,2，然后2,3，然后3,4，然后4,5，然后5,6吗？我进行了调试，但存在一些奇怪的顺序，它跳回并比较1,3。

它到底要比较什么？有什么模式吗？

- cocos2dbeginner

---

它会使用任何有用的“compare”调用序列。您不能依赖顺序。 - user2357112

Javadoc中说明了它使用的算法：http://docs.oracle.com/javase/8/docs/api/java/util/List.html#sort-java.util.Comparator-. 而且源代码也是可用的。但实际上，你不需要关心这些。只要你的比较器遵守比较器接口的契约，你的列表就会被排序。 - JB Nizet

Answer 1

具体的比较取决于内部使用的算法，用于对元素进行排序的Collections.sort方法。根据Collections.sort的Javadoc所述：

“此类中包含的多态算法的文档通常包括实现的简要说明。应将此类说明视为实现说明而非规范的一部分。实现者可以随意替换其他算法，只要遵守规范即可。 （例如，sort使用的算法不必是归并排序，但必须是稳定的。）”

换句话说，Java实现可以自由地使用任何他们喜欢的排序算法，只要它保持相等元素的相对顺序即可。这意味着，如果没有更多关于您特定的Java实现的了解，就无法知道将进行哪些比较。（如果我记得正确，Oracle版本的Java实际上从Java 7到Java 8切换了其Collections.sort的实现，但我可能错了。）

话虽如此，这并不是坏事。编写比较器的想法是告诉排序方法“做任何你需要做的事情来对事物进行排序，如果你需要进行比较，这是方法。”这是一个很好的抽象 - 你说如何排名，魔术黑盒子排序然后使用它来使事物有序。

- templatetypedef

Answer 2

Java 7中Collections.sort的排序算法是插入排序。

- user1901015