java - 为什么归并排序可以比较两个项目两次？

Question

这个问题已经有答案了:

Why does Collections.sort call Comparator twice with the same arguments? (3 个回答)

已关闭 3 年前。

我正在尝试使用“Collections.sort”对数组列表进行排序。

这是我写的代码..

ArrayList<Student> arl = new ArrayList<>();
    arl.add(new Student(1, "tom", 26));
    arl.add(new Student(2, "brown", 22));
    arl.add(new Student(3, "kate", 24));
    arl.add(new Student(4, "brad", 23));
    System.out.println(arl);
    for(Student v : arl) {
        System.out.println(v);
    }
    Collections.sort(arl, new Comparator<Student>(){
        int count = 1;

        public int compare(Student s1, Student s2) {
            System.out.println("**compare "+count++ +" time***");
            System.out.println("s1: "+s1.getName() + "(id: " + s1.getId()+")");
            System.out.println("s2: "+s2.getName() + "(id: " + s2.getId()+")");
            return s1.getName().compareTo(s2.getName());
        }
    });

我得到了一个排序列表，但我好奇的是为什么Java将学生id 3与学生id 2比较两次？我不习惯 Mergesort 的定义，但这是否是因为 Java 是通过称为 Mergesort 的算法进行排序的？

**compare 1 time***
s1: brown(id: 2)
s2: tom(id: 1)
**compare 2 time***
s1: kate(id: 3)
s2: brown(id: 2)
**compare 3 time***
s1: kate(id: 3)
s2: tom(id: 1)
**compare 4 time***
s1: kate(id: 3)
s2: brown(id: 2)
**compare 5 time***
s1: brad(id: 4)
s2: kate(id: 3)
**compare 6 time***
s1: brad(id: 4)
s2: brown(id: 2)

Answer 1

正如我之前所说，您提出的主要问题已经得到解答 here .

您在评论中提出的问题:

On the first comparison, why s1.getName gets the value of 'brown' istead of 'tom'. It compares student id 1 with student id 2 eventually, but it doesn't make sense to me...

它与 Collections.sort 实现直接相关，您可以找到 here (OpenJDK 8) 。在第一个排序阶段，调用 countRunAndMakeAscending 函数，我们可以在其定义中找到以下行:

if (c.compare(a[runHi++], a[lo]) < 0) { // Descending
   ...

这是您传递的比较器第一次被使用，并且碰巧传递给其 compare 方法的第一个参数是索引较高的元素 (a[runHi++]) - 这就是它首先被打印的原因。

在我上面粘贴的链接中，您可以阅读此方法的完整实现。有关整个 Collections.sort 算法的更多信息已在第一个链接中问题的答案中介绍，因此如果您需要进一步的解释，请查看此内容。