[数据结构与算法]自然排序和比较器

Set：无序不可重复

TreeSet：无序可排序，不可重复，不能存储 null 对象的集合，使用 TreeSet 存储对象，对象类要么实现自然排序，要么传递比较器

自然排序：存储进 TreeSet 集合的对象类必须实现 Comparable 接口，重写 comparaTo（），在 comparaTo（）里指定排序规则，返回正数存储的对象往右子树方向，返回负数存储的对象往左子树方向，返回0则不存储

比较器：在创建 TreeSet 集合对象的时候，传递 Comparator 接口的实现类对象，重写 Comparator 接口的 compare（），在compara（）里制定排序规则

自然排序和比较器的区别：

1、使用自然排序需要改变存储对象类的接口

2、使用比较器会额外添加多一个类

3、当比较器与自然排序共存的时候，使用比较器进行排序

import java.util.Iterator;
import java.util.TreeSet;
public class Demo01 {
    public static void main(String[] args) {
        TreeSet<Integer> set = new TreeSet<>();
        set.add(6);
        set.add(4);
        set.add(1);
        set.add(5);
        set.add(3);
        set.add(8);
        set.add(2);
        //迭代器
        Iterator<Integer> it = set.iterator();
        while (it.hasNext()){
            Integer num = it.next();
            System.out.println(num);
        }
        //删除
        set.remove(1);
        System.out.println(set);
        //先删除后添加
        set.remove(4);
        set.add(1);
        System.out.println(set);
    }
}

?使用 TreeSet 存储自定义对象，对象类必须实现 Comparable 接口，重写 comparaTo（），比较规则在方法中

import java.util.TreeSet;

public class Demo02 {
    public static void main(String[] args) {
        TreeSet<User> set = new TreeSet<>();
        set.add(new User(2));
        set.add(new User(1));
        set.add(new User(4));
        set.add(new User(3));
        System.out.println(set);
    }
}

public class User implements Comparable<User> {
    private int id;

    public User() {
    }

    public User(int id) {
        this.id = id;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    @Override
    public String toString() {
        return "User{" +
                "id=" + id +
                '}';
    }

    @Override
    public int compareTo(User user) {
        //根据id从小到大排序
        //return this.getId() - user.getId();
        //根据id从大到小排序
        return user.getId() - this.getId();
    }
}

import java.util.TreeSet;
public class Demo01 {
    public static void main(String[] args) {
        TreeSet<Object> set = new TreeSet<>();
        set.add(new User(1,"小明",16));
        set.add(new User(5,"小红",18));
        set.add(new User(3,"小方",16));
        set.add(new User(6,"小刚",18));
        set.add(new User(7,"小丽",16));
        set.add(new User(4,"小黄",24));
        set.add(new User(8,"小陈",16));
        set.forEach(item -> System.out.println(item));
    }
}

public class User implements Comparable<User>{
    private int id;
    private String name;
    private  int age;

    public User() {
    }

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

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "User{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
    //以 age 从大到小排序，如果 age 相同以 id 从小到大排序
    @Override
    public int compareTo(User user) {
        if(this.getAge() == user.getAge()){
            return this.getId() - user.getId();
        }
        return user.getAge() - this.getAge();
    }
}

import java.util.TreeSet;
//          比较器排序
public class Demo01 {
    public static void main(String[] args) {
        TreeSet<User> set = new TreeSet<>(new MyComparator());
        set.add(new User(1,"小明",16));
        set.add(new User(5,"小红",18));
        set.add(new User(3,"小方",16));
        set.add(new User(6,"小刚",18));
        set.add(new User(7,"小丽",16));
        set.add(new User(4,"小黄",24));
        set.add(new User(8,"小陈",16));
        set.forEach(item -> System.out.println(item));
    }
}

import java.util.Comparator;

public class MyComparator implements Comparator<User> {
    //以 age 从大到小排序，如果 age 相同以 id 从小到大排序
    @Override
    public int compare(User user1, User user2) {
        if (user1.getAge() == user2.getAge()) {
            return user1.getId() - user2.getId();
        }
        return user2.getAge() - user1.getAge();
    }
}

public class User{
    private int id;
    private String name;
    private  int age;

    public User() {
    }

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

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "User{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
 }

import java.util.Comparator;
import java.util.TreeSet;

//匿名内部类完成比较器传递
public class Demo01 {
    public static void main(String[] args) {
        TreeSet<User> set = new TreeSet<>(new Comparator<User>() {
            //以 age 从小到大排序，如果 age 相同以 id 从大到小排序
            @Override
            public int compare(User user1, User user2) {
                if(user1.getAge() == user2.getAge()){
                    return user2.getId() - user1.getId();
                }
                return user1.getAge() - user2.getAge();
            }
        });
        set.add(new User(1,"小明",16));
        set.add(new User(5,"小红",18));
        set.add(new User(3,"小方",16));
        set.add(new User(6,"小刚",18));
        set.add(new User(7,"小丽",16));
        set.add(new User(4,"小黄",24));
        set.add(new User(8,"小陈",16));
        set.forEach(item -> System.out.println(item));
    }
}

public class User{
    private int id;
    private String name;
    private  int age;

    public User() {
    }

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

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "User{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

TreeSet的底层代码：?

?TreeSet的实现过程：

?