Java中自然排序和比较器排序详解
前言
当指执行插入排序、希尔排序、归并排序等算法时，比较两个对象“大小”的比较操作。我们很容易理解整型的i>j这样的比较方式，但当我们对多个对象进行排序时，如何比较两个对象的“大小”呢？这样的比较stu1>stu2显然是不可能通过编译的。为了解决如何比较两个对象大小的问题，JDK提供了两个接口java.lang.Comparable和java.util.Comparator。
一、自然排序：java.lang.Comparable
Comparable接口中只提供了一个方法：compareTo(Objectobj)，该方法的返回值是int。如果返回值为正数，则表示当前对象(调用该方法的对象)比obj对象“大”；反之“小”；如果为零的话，则表示两对象相等。
下面是一个实现了Comparable接口的Student类：
publicclassStudentimplementsComparable{
privateintid;
privateStringname;
publicStudent(){
super();
}
@Override
publicintcompareTo(Objectobj){
if(objinstanceofStudent){
Studentstu=(Student)obj;
returnid-stu.id;
}
return0;
}
@Override
publicStringtoString(){
return"<"+id+","+name+">";
}
}
Student实现了自然排序接口Comparable，那么我们是怎么利用这个接口对一组Student对象进行排序的呢？我们在学习数组的时候，使用了一个类来给整型数组排序：java.util.Arrays。我们使用Arrays的sort方法来给整型数组排序。翻翻API文档就会发现，Arrays里给出了sort方法很多重载形式，其中就包括sort(Object[]obj)，也就是说Arryas也能对对象数组进行排序，排序过程中比较两个对象“大小”时使用的就是Comparable接口的compareTo方法。
publicclassCompareTest{
publicstaticvoidmain(String[]args){
Studentstu1=newStudent(1,"Little");
Studentstu2=newStudent(2,"Cyntin");
Studentstu3=newStudent(3,"Tony");
Studentstu4=newStudent(4,"Gemini");
Student[]stus=newStudent[4];
stus[0]=stu1;
stus[1]=stu4;
stus[2]=stu3;
stus[3]=stu2;
System.out.println(“Array:”+Arrays.toString(stus));
Arrays.sort(stus);
System.out.println(“Sort:”+Arrays.toString(stus));
}
}
Student数组里添加元素的顺序并不是按学号id来添加的。调用了Arrays.sort(stus)之后，对Student数组进行排序，不管sort是使用哪种排序算法来实现的，比较两个对象“大小”这个操作，它是肯定要做的。那么如何比较两个对象的“大小”？Student实现的Comparable接口就发挥作用了。sort方法会将待比较的那个对象强制类型转换成Comparable，并调用compareTo方法，根据其返回值来判断这两个对象的“大小”。所以，在这个例子中排序后的原Student乱序数组就变成了按学号排序的Student数组。
但是我们注意到，排序算法和Student类绑定了，Student只有一种排序算法。但现实社会不是这样的，如果我们不想按学号排序怎么办？假如，我们想按姓名来给学生排序怎么办？我们只能修改Student类的Comparable接口的compareTo方法，改成按姓名排序。如果在同一个系统里有两个操作，一个是按学号排序，另外一个是按姓名排序，这怎么办？不可能在Student类体中写两个compareTo方法的实现。这么看来Comparable就有局限性了。为了弥补这个不足，JDK还为我们提供了另外一个排序方式，也就是下面要说的比较器排序。
二、比较器排序：java.util.Comparator
上面我提到了，之所以提供比较器排序接口，是因为有时需要对同一对象进行多种不同方式的排序，这点自然排序Comparable不能实现。另外，Comparator接口的一个好处是将比较排序算法和具体的实体类分离了。
翻翻API会发现，Arrays.sort还有种重载形式：sort(T[]a,Comparator<?superT>c)，这个方法参数的写法用到了泛型，我们还没讲到。我们可以把它理解成这样的形式：sort(Object[]a,Comparatorc)，这个方法的意思是按照比较器c给出的比较排序算法，对Object数组进行排序。Comparator接口中定义了两个方法：compare(Objecto1,Objecto2)和equals方法，由于equals方法所有对象都有的方法，因此当我们实现Comparator接口时，我们只需重写compare方法，而不需重写equals方法。Comparator接口中对重写equals方法的描述是：“注意，不重写Object.equals(Object)方法总是安全的。然而，在某些情况下，重写此方法可以允许程序确定两个不同的Comparator是否强行实施了相同的排序，从而提高性能。”。我们只需知道第一句话就OK了，也就是说，可以不用去想应该怎么实现equals方法，因为即使我们不显示实现equals方法，而是使用Object类的equals方法，代码依然是安全的。
那么我们来写个代码，来用一用比较器排序。还是用Student类来做，只是没有实现Comparable接口。由于比较器的实现类只用显示实现一个方法，因此，我们可以不用专门写一个类来实现它，当我们需要用到比较器时，可以写个匿名内部类来实现Comparator。
下面是我们的按姓名排序的方法：
publicvoidsortByName(){
Studentstu1=newStudent(1,"Little");
Studentstu2=newStudent(2,"Cyntin");
Studentstu3=newStudent(3,"Tony");
Studentstu4=newStudent(4,"Gemini");
Student[]stus=newStudent[4];
stus[0]=stu1;
stus[1]=stu4;
stus[2]=stu3;
stus[3]=stu2;
System.out.println("Array:"+Arrays.toString(stus));
Arrays.sort(stus,newComparator(){
@Override
publicintcompare(Objecto1,Objecto2){
if(o1instanceofStudent&&o2instanceofStudent){
Students1=(Student)o1;
Students2=(Student)o2;
//returns1.getId()-s2.getId();//按Id排
returns1.getName().compareTo(s2.getName());//按姓名排
}
return0;
}
});
System.out.println("Sorted:"+Arrays.toString(stus));
}
当我们需要对Student按学号排序时，只需修改我们的排序方法中实现Comparator的内部类中的代码，而不用修改Student类。
注意： 当然，你也可以用Student类实现Comparator接口，这样Student就是（isa）比较器了（Comparator）。当需要使用这种排序的时候，将Student看作Comparator来使用就可以了，可以将Student作为参数传入sort方法，因为StudentisaComparator。但这样的代码不是个优秀的代码，因为我们之所以使用比较器（Comparator），其中有个重要的原因就是，这样可以把比较算法和具体类分离，降低类之间的耦合。
TreeSet对这两种比较方式都提供了支持，分别对应着TreeSet的两个构造方法：
1、TreeSet()：根据TreeSet中元素实现的Comparable接口的compareTo方法比较排序
2、TreeSet(Comparatorcomparator)：根据给定的comparator比较器，对TreeSet中的元素比较排序
当向TreeSet中添加元素时，TreeSet就会对元素进行排序。至于是用自然排序还是用比较器排序，就看你的TreeSet构造是怎么写的了。当然，添加第一个元素时不会进行任何比较，TreeSet中都没有元素，和谁比去啊？
下面，分别给出使用两种排序比较方式的TreeSet测试代码：
/**
*使用自然排序
*Student必须实现Comparable接口，否则会抛出ClassCastException
*/
publicvoidtestSortedSet3(){
Studentstu1=newStudent(1,"Little");
Studentstu2=newStudent(2,"Cyntin");
Studentstu3=newStudent(3,"Tony");
Studentstu4=newStudent(4,"Gemini");
SortedSetset=newTreeSet();
set.add(stu1);
set.add(stu3);//若Student没有实现Comparable接口，抛出ClassCastException
set.add(stu4);
set.add(stu2);
set.add(stu4);
set.add(newStudent(12,"Little"));
System.out.println(set);
}
/**
*使用比较器排序
*Student可以只是个简单的Java类，不用实现Comparable接口
*/
publicvoidtestSortedSet3(){
Studentstu1=newStudent(1,"Little");
Studentstu2=newStudent(2,"Cyntin");
Studentstu3=newStudent(3,"Tony");
Studentstu4=newStudent(4,"Gemini");
SortedSetset=newTreeSet(newComparator(){
@Override
publicintcompare(Objecto1,Objecto2){
if(o1instanceofStudent
&&o2instanceofStudent){
Students1=(Student)o1;
Students2=(Student)o2;
returns1.getName().compareTo(s2.getName());
}
return0;
}
});
set.add(stu1);
set.add(stu3);
set.add(stu4);
set.add(stu2);
set.add(stu4);
set.add(newStudent(12,"Little"));
System.out.println(set);
}
另外，介绍个工具类，java.util.Collections。注意，这不是Collection接口。Collections很像Arrays类。Arrays提供了一系列用于对数组操作的静态方法，查找排序等等。Collections也提供了一系列这样的方法，只是它是用于处理集合的，虽然Collections类和Collection接口很像，但是不要被Collections的名字给欺骗了，它不是只能处理Collection接口以及子接口的实现类，同样也可以处理Map接口的实现类。
总结
Java中自然排序和比较器排序的介绍就到这里了，文章介绍的还是相对详细的，希望能对大家的学习或者工作带来一定的帮助，如果有疑问大家可以留言交流。