关于Java排序算法的问题

问题描述 投票:0回答:1

我正在尝试使用'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)
java algorithm collections
1个回答
0
投票

我无法发表评论(我还没有50rep,所以我将在这里回答您的第二个问题。

正如我之前所说,您提出的主要问题已经回答here

您在评论中提出的问题

在第一个比较中,为什么s1.getName获得'brown'而不是'tom'的值。它将学生ID 1和学生ID 2最终进行比较,但是对我来说这没有意义...

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

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

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

在我上面粘贴的链接中,您可以阅读此方法的完整实现。总体上,Collections.sort算法的更多信息已经在第一个链接的问题答案中得到了介绍。

© www.soinside.com 2019 - 2024. All rights reserved.