自然排序VS比较器排序

前言：

一、自然排序

1.1 Integer类型

1.2 String类型

1.3 自定义类Student

compareTo（）方法说明

1.4 练习一

二、比较器排序

2.1 Test中的比较器

2.2 练习二

三、自然排序VS比较器排序

3.1 练习三

四、习题答案

4.1 练习一

4.2 练习二

4.3 练习三

五、扩展

前言：

本篇文章重点讨论TreeSet中的两种排序方式：自然排序VS比较器排序。

感谢大家的观看。

首先，让我们回顾一下TreeSet。

TreeSet的底层是二叉树，所包含的数据具有唯一性，本身也是一个非常高效的集合。

在面对传入的数据时，TreeSet会对其进行排序—–有序。

首先，我们来了解一下在储存我们常用的数据类型：Integer，String时，它会有什么表现。

注意：集合只能存储引用数据类型，面对基本数据类型会自动装箱。

一、自然排序

1.1 Integer类型

代码演示：

public class TestTree {
public static void main(String[] args) {
Set<Integer> tree=new TreeSet<>();
tree.add(1);
tree.add(3);
tree.add(2);
tree.add(7);
tree.add(5);
tree.add(6);
tree.add(11);
tree.add(33);
System.out.println(tree);//[1, 2, 3, 5, 6, 7, 11, 33]会自动排序—大小
}

大家可以看到，我们的TreeSet是有序的，面对Integer类型时，它会按照大小进行排序。

1.2 String类型

代码演示：

Set<String> tree2=new TreeSet<>();
tree2.add("1");
tree2.add("3");
tree2.add("2");
tree2.add("7");
tree2.add("5");
tree2.add("6");
tree2.add("11");
tree2.add("33");
System.out.println(tree2);//[1, 11, 2, 3, 33, 5, 6, 7]按照第一个字符排序

我们这里为了方便大家作比较，选择了与Integer类型采的数据基本保持一致。

大家可以看到，这里我们的字符串是安装第一个字符进行排序。

那么就有人会问，为什么11排在1后面，而不排在1前面？

很简单，因为我们排完第一个，还要排第二个。

所以：

自然排序中的String类型排序规则如下：

–按字符顺序逐位比较；

–区分大小写：

–在排序等级上—-数字>大写字母>小写字母

（0,1,2…）>（A,B,C……）>（a,b,c…）

注意：正如同我们1排在2前面一样，所以A的值（65）是比a的值（97）小的。

0的值为（48）。

'0'（48）< '1'（49）< … < 'Z'（90）< '['（91）< … < 'a'（97）。

1.3 自定义类Student

自定义类（Student）—>抛出异常—>无法确定排序规则–>重写compareTo方法

要搞清楚我们如何将自然排序用在自定义类上，我们就需要知道TreeSet自然排序的原理。

TreeSet 的自然排序（Natural Ordering）基于其存储元素实现的Comparable接口

通过重写Comparable接口中的cmpareTo（）方法，来实现我们不同类型下的自然排序。

所以我们的自定义类要想进行自然排序，也需要接上Comparable接口，重写compareTo（）。

代码演示：

public class Student implements Comparable<Student>{
private String name;
private int age;
private String sex;

//…..构造器，get、set等……

@Override
public String toString() {
return "\\nStudent [name=" + name + ", age=" + age + ", sex=" + sex + "]";
}

@Override
public int compareTo(Student o) {
//重写的自然排序方法
//name
int num;
num=this.name.compareTo(o.name);//调用String类的compareTo
if(num==0){
//name相同
//ages升序排
num=o.age-this.age;
if(num==0){
//age也相同
//sex
num=this.sex.compareTo(o.sex);
}
}
return num;

// return this.age – o.age; // 按年龄升序
}
}

compareTo（）方法说明

返回值类型：int

返回-1： this.value<o.value 当前对象小于目标对象

返回0： this.value=o.value 当前对象等于目标对象

返回1： this.value>o.value 当前对象大于目标对象

注意：小的在前面

在往TreeSet中插入元素时，需要排序+去重。

这点便通过上述对比实现：

(-1)+(+1)—-实现排序

0—-实现去重——为0只保留第一个插入的元素，忽略后续相同元素

对自定义类使用自然排序需要注意：

(1)接口Comparable；

–自定义类 implements Comparable<自定义类>

(2)重写compareTo()；

–public int compareTo(自定义类 o){}

1.4 练习一

用自然排序实现

基础类 Student 属性：name age score 要求将学⽣按照姓名降序、age升序，成绩降序保存到集合中并且名字叫tom的学⽣不管考多少分都位于班级的第⼀位

这部分的内容虽然简单，但大家一定要动手练习。

二、比较器排序

既然，自然排序都如此的全能了，常见的类型和自定义类型它都能解决，那还要我们的比较器排序做什么呢？

当然，既然我们敢把比较器排序拿出来和自然排序碰一碰，那么比较器排序肯定是不逊色于自然排序的。

比如思考以下两个问题：

–如果Student类是第三方提供的类，我们不能修改源代码呢？

–如果我们需要实现不同的排序需求，比如我这一部分功能需要实现升序，另一部分实现降序呢？

如此，是否我们就不能运用我们自然排序的知识了呢？

毕竟自然排序是建立在重写的基础上的，可是现在我们修改Student源代码的权利被剥夺了。

这个时候，便引出了我们现在所学的排序—>比较器排序

2.1 Test中的比较器

——比较器一般写在main方法中，每次使用都需要定义。

步骤：

1.创建一个实现Comparator接口的类；

2.重写compare方法，返回值依旧为-1 0 1；

3.创建一个TreeSet类对象时，将比较器对象作为参数传递给构造函数。

现在让我们分开来看这三点。

第一点和第二点可以结合起来，创建一个实现Comparator接口的类并实现compare方法。

这里我们便可以使用匿名内部类的知识，用匿名内部类代替接口的功能直接实现。

忘记内部类知识的同学可以点击跳转学习一下，很简单。

匿名内部类：Java第十课内部类-CSDN博客

代码演示：

public class TestTree {
public static void main(String[] args) {
//1.创建一个实现Comparator接口的对象
Comparator<Student> comparator=new Comparator<Student>() {
//通过匿名内部类实现Comparator接口功能
//2.重写compara()
@Override
public int compare(Student o1, Student o2) {
int num;
//age升序
num=o1.getAge()-o2.getAge();
if(num==0){
//name降序
num= o2.getName().compareTo(o1.getName());
if(num==0){
//sex升序
num=o1.getSex().compareTo(o2.getSex());
}
}
return num;
}

};
}

第三步创建一个TreeSet对象，将比较器对象作为参数传递进去。

这里我们创建的比较器参数是comparator。

那么话不多说，直接代码演示：

//3.创建一个TreeSet类对象，将比较器对象作为参数传递给构造函数
Set<Student> tree=new TreeSet<>(comparator);

Student s1=new Student("张霄",18,"男");
Student s2=new Student("儿霄",28,"购物袋");
Student s3=new Student("小霄",88,"女");
tree.add(s1);
tree.add(s2);
tree.add(s3);
System.out.println(tree);

Set<Student> tree=new TreeSet<>(comparator);

这一步非常关键一定不能忘记！！！

OK，在大家了解了Comparator后，想必对我们刚才的两个问题也有了答案。

–Comparator便可以在不修改Student源代码的条件下完成排序；

–并且，我们可以创建多个Comparator对象，根据传入TreeSet的参数对象不同，实现不同的排序。

注意：如果自然排序和比较器排序同时存在，比较器排序会覆盖掉自然排序。

毕竟，我们传的参数可不是白传的，显示调用永远压过隐式调用一头。

相信大家已经掌握了比较器排序的方法，我们来试着用一下吧！

2.2 练习二

用比较器排序实现：

将整数1~10实现排序，要求：

–奇数在前，偶数在后；

–奇数升序，偶数降序。

最后输出结果：

三、自然排序VS比较器排序

这两者的区别其实蛮明显的。

自然排序：

–接口：Comparable–重写compareTo方法；

–重写出来的方法只有一个，所以排序规则只有一种；

–定义在类中，实现代码复用。

比较器排序：

–接口：Comparator–重写compare方法；

–可以创建多个对象，多个排序规则；

–不修改源码，但是每次使用都需要定义。

3.1 练习三

将练习一中的题目用比较器排序实现。

基础类 Student 属性：name age score 要求将学⽣按照姓名降序、age升序，成绩降序保存到集合中并且名字叫tom的学⽣不管考多少分都位于班级的第⼀位

四、习题答案

4.1 练习一

基础类 Student 属性：name age score 要求将学⽣按照姓名降序、age升序，成绩降序保存到集合中并且名字叫tom的学⽣不管考多少分都位于班级的第⼀位

Student类：

//自然排序
@Override
public int compareTo(Student o) {
int num;
if(this.name=="tom"){return -1;}
//name降序
num=o.name.compareTo(this.name);
if(num==0){
//age升序
num=this.age-o.age;
if(num==0){
//score降序
num=o.score-this.score;
}
}
return num;
}

Test类：

ublic class Test {
public static void main(String[] args) {

Student s1=new Student("陈霄",18,99);
Student s2=new Student("陈霄",168,989);
Student s3=new Student("女霄",28,999);
Student s4=new Student("tom",17,199);
System.out.println("自然排序——————————————–");
//自然排序
Set<Student> tree1=new TreeSet<>();
tree1.add(s1);
tree1.add(s2);
tree1.add(s3);
tree1.add(s4);
System.out.println(tree1);}}

4.2 练习二

将整数1~10实现排序，要求：

–奇数在前，偶数在后；

–奇数升序，偶数降序。

public class Test {
public static void main(String[] args) {
Comparator<Integer> comparator=new Comparator<Integer>(){
@Override
public int compare(Integer o1, Integer o2){
int num;
if(o1%2!=0){ if(o2%2!=0){num=o1.compareTo(o2); return num; } return -1;}
else { if(o2%2==0){num=o2.compareTo(o1);return num;} return 1;}
}
};

Set<Integer> tree=new TreeSet<>(comparator);
for(int i=1;i<=10;i++){
tree.add(i);
}
System.out.println(tree);

}
}

4.3 练习三

比较器排序实现练习一：

基础类 Student 属性：name age score 要求将学⽣按照姓名降序、age升序，成绩降序保存到集合中并且名字叫tom的学⽣不管考多少分都位于班级的第⼀位

//比较器排序
Comparator<Student> comparator=new Comparator<Student>() {

@Override
public int compare(Student o1, Student o2) {
int num;
if(o1.getName()=="tom"){return -1;}
//name降序
num=o2.getName().compareTo(o1.getName());
if(num==0){
//age升序
num=o1.getAge()-o2.getAge();
if(num==0){
//score降序
num=o2.getScore()-o1.getScore();
}
}
return num;
}
};
Set<Student> tree2=new TreeSet<>(comparator);
tree2.add(s1);
tree2.add(s2);
tree2.add(s3);
tree2.add(s4);
System.out.println(tree2);

五、扩展

这里整理一下不同集合的排序规则。

我们目前学了ArrayList，LinkedList，HashSet，LinkedHashSet，TreeSet。

集合类型排序方式排序依据 / 规则

ArrayList	需手动排序	插入顺序（默认）；Collections.sort()自定义
LinkedList	需手动排序	插入顺序（默认）；Collections.sort()自定义
HashSet	不排序	无序（哈希表实现）
LinkedHashSet	固定排序	插入顺序（链表维护）
TreeSet	自动排序	自然排序（Comparable）或比较器（Comparator）

大家也可以看出来，我们的排序基本分为三种。

通过理解这些规则，可根据实际需求选择合适的集合：需顺序用LinkedHashSet，需排序用TreeSet，仅去重无序用HashSet，动态列表用ArrayList/LinkedList。

当然，我们后续还会学习Map，有了Map的加入，我们的选择又会多起来。

OK，这篇文章便到此结束！

星辰亦有远方；

彼时的你又心向谁呢？