欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java中自然排序和比较器排序详解

程序员文章站 2024-03-13 14:59:21
前言 当指执行插入排序、希尔排序、归并排序等算法时,比较两个对象“大小”的比较操作。我们很容易理解整型的 i>j 这样的比较方式,但当我们对多个对象进行排序时,如何...

前言

当指执行插入排序、希尔排序、归并排序等算法时,比较两个对象“大小”的比较操作。我们很容易理解整型的 i>j 这样的比较方式,但当我们对多个对象进行排序时,如何比较两个对象的“大小”呢?这样的比较 stu1 > stu2 显然是不可能通过编译的。为了解决如何比较两个对象大小的问题,jdk提供了两个接口 java.lang.comparable java.util.comparator

一、自然排序:java.lang.comparable

comparable 接口中只提供了一个方法: compareto(object obj) ,该方法的返回值是 int 。如果返回值为正数,则表示当前对象(调用该方法的对象)比 obj 对象“大”;反之“小”;如果为零的话,则表示两对象相等。

下面是一个实现了 comparable 接口的 student 类:

public class student implements comparable { 
 
 private int id; 
  
 private string name; 
 
 public student() { 
  super(); 
 } 
 
 @override 
 public int compareto(object obj) { 
  if (obj instanceof student) { 
   student stu = (student) obj; 
   return id - stu.id; 
  } 
  return 0; 
 } 
 
 @override 
 public string tostring() { 
  return "<" + id + ", " + name + ">"; 
 } 
} 

student 实现了自然排序接口 comparable ,那么我们是怎么利用这个接口对一组 student 对象进行排序的呢?我们在学习数组的时候,使用了一个类来给整型数组排序: java.util.arrays 。我们使用 arrays 的 sort 方法来给整型数组排序。翻翻 api 文档就会发现, arrays 里给出了 sort 方法很多重载形式,其中就包括 sort(object[] obj) ,也就是说 arryas 也能对对象数组进行排序,排序过程中比较两个对象“大小”时使用的就是 comparable 接口的 compareto 方法。

public class comparetest { 
 
 public static void main(string[] args) { 
  student stu1 = new student(1, "little"); 
  student stu2 = new student(2, "cyntin"); 
  student stu3 = new student(3, "tony"); 
  student stu4 = new student(4, "gemini"); 
   
  student[] stus = new student[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<? super t> c) ,这个方法参数的写法用到了泛型,我们还没讲到。我们可以把它理解成这样的形式: sort(object[] a, comparator c) ,这个方法的意思是按照比较器 c 给出的比较排序算法,对 object 数组进行排序。comparator 接口中定义了两个方法: compare(object o1, object o2) equals 方法,由于 equals 方法所有对象都有的方法,因此当我们实现 comparator 接口时,我们只需重写 compare 方法,而不需重写 equals 方法。comparator 接口中对重写 equals 方法的描述是:“注意,不重写 object.equals(object) 方法总是安全的。然而,在某些情况下,重写此方法可以允许程序确定两个不同的 comparator 是否强行实施了相同的排序,从而提高性能。”。我们只需知道第一句话就ok了,也就是说,可以不用去想应该怎么实现 equals 方法,因为即使我们不显示实现 equals 方法,而是使用object类的 equals 方法,代码依然是安全的。

那么我们来写个代码,来用一用比较器排序。还是用 student 类来做,只是没有实现 comparable 接口。由于比较器的实现类只用显示实现一个方法,因此,我们可以不用专门写一个类来实现它,当我们需要用到比较器时,可以写个匿名内部类来实现 comparator 。

下面是我们的按姓名排序的方法:

public void sortbyname () { 
 student stu1 = new student(1, "little"); 
 student stu2 = new student(2, "cyntin"); 
 student stu3 = new student(3, "tony"); 
 student stu4 = new student(4, "gemini"); 
  
 student[] stus = new student[4]; 
 stus[0] = stu1; 
 stus[1] = stu4; 
 stus[2] = stu3; 
 stus[3] = stu2; 
 system.out.println("array: " + arrays.tostring(stus)); 
 
 arrays.sort(stus, new comparator() { 
 
  @override 
  public int compare(object o1, object o2) { 
   if (o1 instanceof student && o2 instanceof student) { 
    student s1 = (student) o1; 
    student s2 = (student) o2; 
    //return s1.getid() - s2.getid(); // 按id排 
    return s1.getname().compareto(s2.getname()); // 按姓名排 
   } 
   return 0; 
  } 
   
 }); 
  
 system.out.println("sorted: " + arrays.tostring(stus)); 
} 

当我们需要对student按学号排序时,只需修改我们的排序方法中实现comparator的内部类中的代码,而不用修改 student 类。

注意: 当然,你也可以用 student 类实现 comparator 接口,这样student就是(is a)比较器了(comparator)。当需要使用这种排序的时候,将 student 看作 comparator 来使用就可以了,可以将 student 作为参数传入 sort 方法,因为 student is a comparator 。但这样的代码不是个优秀的代码,因为我们之所以使用比较器(comparator),其中有个重要的原因就是,这样可以把比较算法和具体类分离,降低类之间的耦合。

treeset对这两种比较方式都提供了支持,分别对应着treeset的两个构造方法:

     1、treeset():根据treeset中元素实现的 comparable 接口的 compareto 方法比较排序

   2、treeset(comparator comparator):根据给定的 comparator 比较器,对 treeset 中的元素比较排序

当向 treeset 中添加元素时,treeset 就会对元素进行排序。至于是用自然排序还是用比较器排序,就看你的 treeset 构造是怎么写的了。当然,添加第一个元素时不会进行任何比较, treeset 中都没有元素,和谁比去啊?

下面,分别给出使用两种排序比较方式的 treeset 测试代码:

/** 
 * 使用自然排序 
 * student必须实现comparable接口,否则会抛出classcastexception 
 */ 
public void testsortedset3() { 
 student stu1 = new student(1, "little"); 
 student stu2 = new student(2, "cyntin"); 
 student stu3 = new student(3, "tony"); 
 student stu4 = new student(4, "gemini"); 
 
 sortedset set = new treeset(); 
 set.add(stu1); 
 set.add(stu3); // 若student没有实现comparable接口,抛出classcastexception 
 set.add(stu4); 
 set.add(stu2); 
 set.add(stu4); 
 set.add(new student(12, "little")); 
 
 system.out.println(set); 
} 
/** 
 * 使用比较器排序 
 * student可以只是个简单的java类,不用实现comparable接口 
 */ 
public void testsortedset3() { 
 student stu1 = new student(1, "little"); 
 student stu2 = new student(2, "cyntin"); 
 student stu3 = new student(3, "tony"); 
 student stu4 = new student(4, "gemini"); 
 
 sortedset set = new treeset(new comparator() { 
 
  @override 
  public int compare(object o1, object o2) { 
   if (o1 instanceof student 
     && o2 instanceof student) { 
    student s1 = (student) o1; 
    student s2 = (student) o2; 
    return s1.getname().compareto(s2.getname()); 
   } 
   return 0; 
  } 
   
 }); 
 
 set.add(stu1); 
 set.add(stu3); 
 set.add(stu4); 
 set.add(stu2); 
 set.add(stu4); 
 set.add(new student(12, "little")); 
 
 system.out.println(set); 
} 

另外,介绍个工具类,java.util.collections。注意,这不是collection接口。collections很像arrays类。arrays提供了一系列用于对数组操作的静态方法,查找排序等等。collections也提供了一系列这样的方法,只是它是用于处理集合的,虽然collections类和collection接口很像,但是不要被collections的名字给欺骗了,它不是只能处理collection接口以及子接口的实现类,同样也可以处理map接口的实现类。

总结

java中自然排序和比较器排序的介绍就到这里了,文章介绍的还是相对详细的,希望能对大家的学习或者工作带来一定的帮助,如果有疑问大家可以留言交流。