[数据结构与算法]TreeSet排序（详细解析）

目录

一，首先我们来看以下代码

二，异常产生

三，解决异常

四，排序原理

五，代码示例

总结（TreeSet集合排序）

都知道TreeSet集合的特点是：

• 元素不重复

• 元素有序

但具体为什么元素有序，按照什么规则排序大家知道吗？ 今天要说的就是排序，内容如有错误欢迎指正，谢谢！

一，首先我们来看以下代码

?public class TreeSet_01 {
? ? ?public static void main(String[] args) {
? ? ? ? ?TreeSet<Integer> treeSet = new TreeSet<Integer>();
??
? ? ? ? ?treeSet.add(10);
? ? ? ? ?treeSet.add(20);
? ? ? ? ?treeSet.add(50);
? ? ? ? ?treeSet.add(10);
? ? ? ? ?treeSet.add(90);
??
? ? ? ? ?for (Integer i : treeSet) {
? ? ? ? ? ? ?System.out.print(i+" ");
? ? ? ?  }
? ? ? ? ?//输出四个元素，且没有重复，顺序依次从小到大，这里用的是TreeSet(){}无参构造方法，默认自然排序
?//
?//总结
?// ? ? ?  1.元素不重复这是因为是Set集合，底层是由哈希表实现，则不重复
?// ? ? ?  2.顺序依次从小到大，这是默认自然排序的结果
? ?  }
?}

把Integer存入TreeSet集合中，很简单吧！

再看下面的代码

二，异常产生

这里我们尝试将Student存入TreeSet中

public class TreeSet_02 {
    public static void main(String[] args) {
        TreeSet<Student> treeSet = new TreeSet<>();//创建一个TreeSet集合
        //分别创建几个学生对象
        Student s1 = new Student("袁治伟", 30);
        Student s2 = new Student("张友龙", 22);
        Student s3 = new Student("马艳丽", 25);
        Student s4 = new Student("德华", 40);
        //把学生对象添加进集合
        treeSet.add(s1);
        treeSet.add(s2);
        treeSet.add(s3);
        //增强for遍历输出，这里我重写了ToSting方法所以直接输出s
        for (Student s:treeSet){
            System.out.println(s);
        }
    }
}

public class Student implements Comparable<Student>{
? ? ?String name;
? ? ?int age;
??
? ? ?public Student() {
? ?  }
??
? ? ?public Student(String name, int age) {
? ? ? ? ?this.name = name;
? ? ? ? ?this.age = age;
? ?  }
??
? ? ?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 "Student{" +
? ? ? ? ? ? ? ? ?"name='" + name + '\'' +
? ? ? ? ? ? ? ? ?", age=" + age +
? ? ? ? ? ? ? ? ?'}';
? ?  }
?}

重写ToSting方法

学生类中重写的ToSting方法，这样的好处是当你Print学生对象的时候不用调用get方法，可以直接print（学生对象）

运行结果：

类转换异常

三，解决异常

首先我们分析原因

学生类不能转换成一个java.lang.Comparable，这样一个东西，我们去帮助文档中查看一下

显然Comparable是一个接口，它对实现它的每个类的对象强加一个整体排序，给这个类加一个自然排序，这里我们可以浅显的理解为单纯的就是数字从小到大的一个排序，这里我们还是举出我们第一个代码的例子

public class TreeSet_01 {
    public static void main(String[] args) {
        TreeSet<Integer> treeSet = new TreeSet<Integer>();

        treeSet.add(20);
        treeSet.add(50);
        treeSet.add(10);
        treeSet.add(90);

        for (Integer i : treeSet) {
            System.out.print(i+" ");
        }

这里输出的是10 20 50 90，很明显输出的时候做了从小到大的一个排序，但问题是我所要排序的可不是数字了，而是学生对象Student，所以本来给的默认自然排序方法不可行了

Comparable需要对实现它的每类的对象加一个排序，对实现它的每个类的对象排序，我们的Student类都不是实现它的类啊，所以我们第一步应该实现这个接口

实现接口的时候记得重写其中的方法这里是CompareTo方法

这里可能有好奇的同学就要问了，那Integer也没有实现Comparable接口啊，那为什么它不用重写CompareTo就可以完成排序，这里我查了一下文档，显然Integer也实现了Comparable接口

为了一会说排序大家不晕我们需要说一下这里的返回值的意思

return 0;(两个元素一样，不需要存储)

return 正整数;(两个元素不同，后者大于前者直接存储在集合后面）

return 负数;(两个元素不同，后者小于前者，该元素需存储在前面)

注意：这里后者前者

前者：被比较的元素

后者：比较的元素

具体验证我们看下面的代码

1.return 0;

?

我们发现只存储的一个元素，为什么呢?其实很好理解，调用add方法的时候会进行比较，因为TreeSet集合存储元素的时候它需要保证元素唯一且有序，这是TreeSet集合的特点，具体不做解释，第一个元素没人和它比直接存进来，第二个元素开始和第一个比直接return 0，认为两个元素一样，则不存，依次类推，最终只存了一个元素。

2.return 正整数；

都存储进来了，而且顺序就是我们add的顺序，因为返回值是正数，代表后者总比前者大，所以它就没改变次序依次存储进来

3.return 负数;

注意看这里我们先存的是袁治伟，但最后输出的才是袁治伟，这也很好理解，因为返回值是负数，所以每次比较都认为是后者小于前者，则把后者放前面，则最后面的就到了最前，但这里我也发现了一个小小的问题，就是如果每次比较一次的话最终的结果不应该是这个样子，我们看下图

红色框内才是我们程序运行的结果，和我们预想的不符，如果按照后一个和前一个比较就到前面应该是 张-->马-->袁，说明比较了不止一次，应该是后面add的元素和前面的每一个元素比较并调换顺序，这里的内容仅仅个人理解，真实内容可以去参考源码

四，排序原理

了解了返回值对排序结果的影响后，我们还是不知道TreeSet的排序原理，我们继续先做一个作业，添加一个学生，刘德华，年龄25，让这四个学生按年龄排序

按年龄排序简单啊，比较年龄大小就ok了，来我们试试

这里我们用后者的年龄减去前者的年龄如果为负数，则说明后者年龄小把后者排在前者前面，如果有不理解的可以先看一下这个图

（一）按年龄排序

@Override
?public int compareTo(Student o) {
? ? ?return this.age-o.age;
?}

从运行结果来看成功了，但没完全成功，因为刘德华不见了，为什么呢？我们看返回值return this.age-o.age;年龄差，刘德华和马艳丽年龄相同，返回值是0，前面我们说过，如果返回值是0，那么会认为两个元素相同不需要存储，如何解决这个这个问题呢，也就是当年龄相同的时候我们能根据姓名有一定顺序的存储，我们来看看下面的代码

（二）按名字排序

? @Override
? ? ?public int compareTo(Student o) {
? ? ? ? ?int num = this.name.compareTo(o.name);
? ? ? ? ?return num;
? ?  }
?}

这是直接跟 根据姓名存储，这里用到了this.name.compareTo(o.name)，这里的this.name其实就是后者的名字，是个字符串，也就是调用了String的compareTo方法，我们去帮助文档中看一下这个方法

?

这里说的比较字符串的Unicode值，如何理解呢，我们可以看看下面的代码

输出的结果来看，我们看不出来是怎么排序的，我们根据上面的帮助文档中的描述，是字符串的Unicode编码排序，我们可以验证一下

分别计算了四个人的姓氏的Unicode编码，我们不难看出从小到大的排序为

21016-->刘

24352-->张

34945-->袁

39532-->马

和我们上面的输出结果顺序一致

Student{name='刘德华', age=25} Student{name='张友龙', age=22} Student{name='袁治伟', age=30} Student{name='马艳丽', age=25}

证明了字符串确实是按照计算该字符串的第一个字符的Unicode编码排序

我们对帮助文档中的内容一一验证

1.英文字母的排序

意思就是返回值=两个英文的首字母的差值

比如a和b差值为1

a和c差值为2

a和z差值为25

public class TreeSet_02 {
? ? ?public static void main(String[] args) {
? ? ? ? ?TreeSet<Student> treeSet = new TreeSet<>();//创建一个TreeSet集合
? ? ? ? ?//分别创建几个学生对象
? ? ? ? ?Student s1 = new Student("yuanzhiwei", 30);
? ? ? ? ?Student s2 = new Student("zhangyoulong", 22);
? ? ? ? ?Student s3 = new Student("mayanli", 25);
? ? ? ? ?Student s4 = new Student("liudehua", 25);
? ? ? ? ?//把学生对象添加进集合
? ? ? ? ?treeSet.add(s1);
? ? ? ? ?treeSet.add(s2);
? ? ? ? ?treeSet.add(s3);
? ? ? ? ?treeSet.add(s4);
? ? ? ? ?//增强for遍历输出，这里我重写了ToSting方法所以直接输出s
? ? ? ? ?for (Student s:treeSet){
? ? ? ? ? ? ?System.out.println(s);
? ? ? ?  }
? ?  }
?}

上面的运行结果很明显四个同学的排序是按照名字的英文首字母排序的，证明了上面的结论正确

2.按字符串长度排序

这个好理解就是哪个字符串的长度短就排在前面，这时这个返回值就是两个字符串长度的差值

public class TreeSet_02 {
? ? ?public static void main(String[] args) {
? ? ? ? ?TreeSet<Student> treeSet = new TreeSet<>();//创建一个TreeSet集合
? ? ? ? ?//分别创建几个学生对象
? ? ? ? ?Student s1 = new Student("yuanzhiwei", 30);
? ? ? ? ?Student s2 = new Student("zhangyoulong", 22);
? ? ? ? ?Student s3 = new Student("mayanli", 25);
? ? ? ? ?Student s4 = new Student("liudehua", 25);
? ? ? ? ?Student s5 = new Student("mayanliz",25);
? ? ? ? ?//把学生对象添加进集合
? ? ? ? ?treeSet.add(s1);
? ? ? ? ?treeSet.add(s2);
? ? ? ? ?treeSet.add(s3);
? ? ? ? ?treeSet.add(s4);
? ? ? ? ?treeSet.add(s5);
? ? ? ? ?//增强for遍历输出，这里我重写了ToSting方法所以直接输出s
? ? ? ? ?for (Student s:treeSet){
? ? ? ? ? ? ?System.out.println(s);
? ? ? ?  }
? ?  }
?}

明显mayanliz排在了mayanli的后面，因为他们已有的字符串是一样的，那么就比长度，短的在前

五，代码示例

 @Override
? ? ?public int compareTo(Student o) {
? ? ? ? ?int num;
? ? ? ? ?if (this.age-o.age==0){
? ? ? ? ? ? ?num = this.name.compareTo(o.name);
? ? ? ?  }else {
? ? ? ? ? ? ?num = this.age-o.age;
? ? ? ?  }
? ? ? ? ?return num;
? ?  }
?}

上面的重写xompraeTo方法按照年龄排序且如果年龄相同则根据名字排序，我们测验一下

ok，结果没有任何问题，相信大家已经完全弄懂了TreeSet集合的排序

总结（TreeSet集合排序）

1.首先考虑字符首字母，按照A—Z排序，如果首字母相同再看下一位字母，以此类推，此时camparaTo方法的返回值是两个字母的Unicode差值，如果不是字母，则同样按照Unicode编码排序，小的在前面

2.若字母相同，例如Student和Students比较，已有的字母相同，那么会继续比较字符串的长度，短的排前面，此时的camparaTo方法的返回值是两个字符串长度的差

3.第一次写这种笔记，每次学习一个新的内容的时候最快乐的就是验证自己的猜想，每当验证自己的猜想正确的时候总会有一种莫大的成就感，将会成为我继续学习下去的动力，上述内容如若有误欢迎指正，共同进步！