• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

java进阶–Java中comparator及comparable完全解析

java 来源:HankingHu 4次浏览

comparator具体用法

先举一个例子说明comparator的用法。假设武器库里有许多的枪,这些枪有两个重要指标一个是长度(len),另一个是威力(pow),现在对这些枪有个评价标准是:在威力相同的情况下长度越短越好,威力不同的情况下威力越大越好,对这些枪进行排序。

分析: 题目中同时对两个变量进行比较并且比较的方式还不一样,pow是由大到小排序,而len是由小到大排序。如果利用现有的容器里的比较方法是不能实现的,通过实现comparator接口就可以很容易的实现比较了。先实现上面的例子,然后再讲解原因。

class Weapon {
    int len;
    int pow;
    public Weapon(int len, int pow) {       
        this.len = len;
        this.pow = pow;
    }
    //weapon 两个值,一个len,一个pow 
}

① 上面是weapon类有两个成员变量分别是len 和 pow。

class WeaponComparator implements Comparator<Weapon> { 
    @Override
    public int compare(Weapon o1, Weapon o2) {
        if(o1.pow<o2.pow)
            return 1;
        //返回1表示当 o1.pow<o2.pow时,o1会在o2的后面,o2会排在前面。后面会详细解析为什么。

        if(o1.pow==o2.pow)
        {
        //在pow相同的情况下,按len的大小从小到大排序
            if(o1.len>o2.len)
            {
                return 1;

            }
            if(o1.len==o2.len) {
                return 0;               
            }           
                return -1;              
        }       
        return -1;
    }   
}

②上面的比较器实现了comparator接口。且用len和pow两个值定义了比较规则。

public class ComparatorTest {


    public static void main(String[] args) {

        int arr[][]={
  {
  1,2},{
  2,3},{
  1,3},{
  2,2},{
  3,4},{
  2,4}};
        Weapon weapons[]=new Weapon[arr.length];
        for(int i=0;i<arr.length;i++)
        {
            weapons[i]=new Weapon(arr[i][0], arr[i][1]);
        }
        //生成一个weapon数组
        WeaponComparator wComparator=new WeaponComparator();
        //定义一个比较器
        Arrays.sort(weapons,wComparator );
        //Arrays.sort(weapons,wComparator );对weapons进行排序
        for(int i=0;i<arr.length;i++)
        {
            System.out.println(weapons[i].pow+" "+weapons[i].len);
        }       
    }
}

③上面定义一个weapon类型的数组,然后利用Arrays.sort传入自定义的比较器和weapons数组进行排序。

//输出
/* weapon len 4 2 4 3 3 1 3 2 2 1 2 2 */

④由输出可以看出按照pow从大到小排序,在pow相同的情况下按照 len 从小到大排序。

总结一下:comparator用法其实很简单,只要实现comparator接口中的compare方法并且在里面实现自己的比较逻辑,然后调用排序类进行排序。

深入理解comparator

public interface Comparator<T> {

    int compare(T o1, T o2);

    boolean equals(Object obj);

}

comparator是一个接口,里面compare和equals方法,一般实现自己的比较逻辑时,只要重写int compare(T o1, T o2);方法就可以了,compare有三个返回值,-1,0,1,在重写的时候一定要注意,排序的时候会利用这三个值的。再来看看Arrays.sort( arr[] ,comparator )到底是怎么实现的,为什么能够实现自定义的排序。下面是做了一定简化的代码:

 public static <T> void sort(T[] a, Comparator<? super T> c) {
        T[] aux = a.clone();
        mergeSort(aux, a, 0, a.length, c);
    }

原来sort 方法调用了 mergeSort 合并排序。下面看看 mergeSort的实现。

private static void mergeSort(Object[] src,
                                  Object[] dest,
                                  int low, int high, int off,
                                  Comparator c) {
        int length = high - low;

        // 如果数组的长度小于7时就使用插入排序
        if (length < 7) {
            for (int i=low; i<high; i++)
                for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)
                    swap(dest, j, j-1);
            return;
            //在插入排序中的判断大小的方法原来就是自定义的comparator中的compare方法
            //c.compare(dest[j-1], dest[j])>0
        }

        //如果长度大于7就递归的对其左右进行排序
        int destLow  = low;
        int destHigh = high;
        low  += off;
        high += off;
        int mid = (low + high) >>> 1;
        mergeSort(dest, src, low, mid, -off, c);
        mergeSort(dest, src, mid, high, -off, c);

        // 如果排好序的左边的最大元素小于排好序的右边的最小元素则可以知道从low到high都已经排好序了
        //直接复制到src数组中就行了
        if (c.compare(src[mid-1], src[mid]) <= 0) {
           System.arraycopy(src, low, dest, destLow, length);
           return;
        }

        //否则还是利用自定义的comparator中的compare方法来比较大小,对将左右两边的数组进行合并排序
        for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
            if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
    }

下面是插入排序中的swap()方法。

private static void swap(Object[] x, int a, int b) {
        Object t = x[a];
        x[a] = x[b];
        x[b] = t;
    }

上面的代码进行几点说明:
①上面的MergeSort方法对平常的MergeSort方法进行了优化。
②如果数组的长度小于7时直接调用了插入排序,这样速度更快,这里说的数组长度包括递归时左右子数组的长度。
③每次对左右子数组排序后,先判断左边的数组是不是都比右边的小,这个很好判断上面只用了一句话: if (c.compare(src[mid-1], src[mid]) <= 0) 如果是的,直接复制到数组中就可以,不用再进行一次排序。这样可以节约时间。

Comparable

下面用Comparable方式实现 weapon的排序。

//weapon直接实现了Comparable接口并且重写了compareTo方法,比较逻辑在compareTo方法里。
class Weapon implements Comparable<Weapon> { 
    int len;
    int pow;
    public Weapon(int len, int pow) {       
        this.len = len;
        this.pow = pow;
    }
    @Override
    public int compareTo(Weapon o) {
        if(this.pow<o.pow)
            return 1;
        if(this.pow==o.pow)
        {
            if(this.len>o.len)
            {
                return 1;
            }
            if(this.len==o.len) {
                return 0;               
            }           
                return -1;              
        }       
        return -1;

    }

再看看如何对weapon排序的。

//直接调用Arrays.sort(weapons);就可以完成对weapon排序。
public class ComparableTest {

    public static void main(String[] args) {
        int arr[][]={
  {
  1,2},{
  2,3},{
  1,3},{
  2,2},{
  3,4},{
  2,4}};
        Weapon weapons[]=new Weapon[arr.length];
        for(int i=0;i<arr.length;i++)
        {
            weapons[i]=new Weapon(arr[i][0], arr[i][1]);
        }
        Arrays.sort(weapons);
        for(int i=0;i<arr.length;i++)
        {
            System.out.println(weapons[i].pow+" "+weapons[i].len);
        }   
    }

}

有上面代码可知
①定义类时实现comparable接口,并且在compareTo中实现比较大小的逻辑。就可以调用Arrays.sort()来实现排序。也可以用Collections.sort()来实现排序。
②如果某个类实现了comparable接口那么它的比较逻辑就确定了,不能更改了,比如说String中的compareTo()方法中实现了比较字符串的逻辑,那么对字符串数组进行比较大小时会调用这个比较方法,如果要改变这种比较方式,就定义一个StringComparator比较器,并实现compare方法。调用Arrays.sort时传入这个比较器就可以了。
③Comparator接口其实是对comparable的一种扩展,更方便用户自定义多种比较逻辑。

原来Arrays.sort中利用我们自定义的比较大小的方法来进行排序,也就是调用了我们实现Comparator接口中的compare方法来实现排序的。如果没有传入定义的Comparator,那么对象必须实现comparable接口才能够比较大小,不然无法将对象进行排序,在Java中 Integer,String,double 等都实现了comparable接口所以可以直接比较大小。


版权声明:本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。
喜欢 (0)