Collections.Sort详解(2大排序用法及底层原理)

Collections.Sort详解(2大排序用法及底层原理)-mikechen

Collections.Sort在Java集合经常使用,但是很多同学并不了解Collections.Sort的具体用法以及底层原理,下面详解。

Collections.Sort简介

Collections.sort() 是 Java 中 Collections 类提供的一个静态方法,用于对一个实现了 List 接口的集合进行升序排序。

 

Collections.Sort用法

Collections.sort主要有两种用法,一种是采用自然顺序排序,一种是自定义排序规则。

1.自带排序

例如在List集合中,我们我们可以使用Collections.sort(list)自带的排序方法给集合排序,不用自己写排序算法了。

如下所示:

List numbers = new ArrayList<>();
numbers.add(5);
numbers.add(2);
numbers.add(9);
numbers.add(1);

Collections.sort(numbers);
System.out.println(numbers);

输出:

[1, 2, 5, 9]

我们可以看见,Collections.sort() 方法使用元素的自然顺序进行排序好了。

 

2.自定义排序

如果需要使用不同的排序规则,可以传入一个自定义的 Comparator 对象来实现,如下所示:

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Person {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }

    public static void main(String[] args) {
        List persons = new ArrayList<>();
        persons.add(new Person("Tom", 20));
        persons.add(new Person("Bob", 25));
        persons.add(new Person("Alice", 18));
        persons.add(new Person("Mary", 22));

        Comparator ageComparator = new Comparator() {
            @Override
            public int compare(Person p1, Person p2) {
                return Integer.compare(p1.getAge(), p2.getAge());
            }
        };

        Collections.sort(persons, ageComparator);

        for (Person person : persons) {
            System.out.println(person.getName()   ", "   person.getAge());
        }
    }
}

上面我们有一个Person类,包含了姓名和年龄两个属性,我们希望按照年龄从小到大的顺序对 Person 对象进行排序。

我们使用一个匿名内部类来实现自定义的 Comparator,这个 Comparator 的实现规则是:按照 Person 对象的年龄属性进行比较。

最后,我们通过调用 Collections.sort() 方法来对 persons 列表进行排序,这就是 Collections.sort的自定排序规则的用法。

 

Collections.Sort实现原理

那你是否对Collections.sort()如何排序感兴趣呢,我们扒一下sort()的源码:

Collections.Sort详解(2大排序用法及底层原理)-mikechen

发现里面用到了ComparableTimSort.sort,底层属于归并排序(Merge Sort)算法。

Java 中的 Collections.sort() 具体实现是通过对集合元素进行分治,递归排序,再合并排序结果的方式来实现的。

具体来说,排序的过程如下:

  1. 将集合按照中间位置分成两个部分;
  2. 对左边部分和右边部分分别进行递归排序;
  3. 对已排序的两部分进行合并排序。

在实现上,归并排序可以通过一个辅助数组来存储排序结果,最后再将排序结果复制回原数组。

以上就是Collections.Sort详解,更多Java集合框架,请查看:Java集合框架详解(看这篇就够了)

作者简介

陈睿|mikechen,10年+大厂架构经验,BAT资深面试官,就职于阿里巴巴、淘宝、百度等一线互联网大厂。

👇阅读更多mikechen架构文章👇

阿里架构 |双11秒杀 |分布式架构 |负载均衡 |单点登录 |微服务 |云原生 |高并发 |架构师

以上

关注作者「mikechen」公众号,获取更多技术干货!

后台回复架构,即可获取《阿里架构师进阶专题全部合集》,后台回复面试即可获取《史上最全阿里Java面试题总结

评论交流
    说说你的看法