Java 对象比较

Java

分出大小高低

比较接口

java.lang.Comparable接口
只接受一个参数，表示内置比较，对象和外来对象比较
分别返回负数，0和正数表示小于，等于和大于

Comparable.java
1
2
3
public interface Comparable<T> {
    public int compareTo(T o);
}

java.util.Comparator接口
接受两个参数，表示外置比较，两个外来对象比较

Comparator.java
1
2
3
4
5
6
7
@FunctionalInterface
public interface Comparator<T> {
    int compare(T o1, T o2);

    boolean equals(Object obj);
    //...
}

注意函数式接口Comparator还有一个equals方法，似乎违反了唯一方法约束。这是因为equals方法属于Object方法，不算违反。一般实现Comparator也不会实现equals方法，因为Object自带实现。当两个不同的比较器默认是不相等的，如果产生相同排序结果时，可以考虑重新实现这个方法。

正确比较

正确的比较应该满足

  • 自反性 x.compareTo(x) == 0 并且 x.compareTo(y) 和 y.compareTo(x) 符号相反
  • 传递性 x.compareTo(y) > 0 && y.compareTo(z) > 0 => x.compareTo(z) > 0
  • 对称性 x.compareTo(y) == 0 => x.compareTo(z) 和 y.compareTo(z) 符号相同

数值运算可能溢出，导致异常结果

1
2
3
4
5
Comparator<Integer> cmp = new Comparator<Integer>(){
    public int compare(Integer i1,Integer i2){
        return i2 - i1;
    }
}

Integer内部是用三元运算比较实现

Integer.java
1
2
3
4
5
6
public int compareTo(Integer anotherInteger) {
    return compare(this.value, anotherInteger.value);
}
public static int compare(int x, int y) {
    return (x < y) ? -1 : ((x == y) ? 0 : 1);
}

没有正确实现比较，在JDK7之后的排序算法可能报出
java.lang.IllegalArgumentException: Comparison method violates its general contract!

数组集合排序

Arrays.sort 只有对象类型才可以自定义比较器，基本类型只可以默认升序
基本类型数组不能生效因为没有泛型，采取从末尾遍历的方法变通
Collection.sort 由于集合只支持对象类型，可以传Comparator.reversed()实现降序

针对基本类型，采用双轴快排

Arrays.java
1
2
3
public static void sort(int[] a) {
    DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}

针对对象类型，早期是归并排序，现在是Tim排序, 结合使用归并和插入

Arrays.java
1
2
3
4
5
6
7
8
9
10
11
12
public static void sort(Object[] a) {
    if (LegacyMergeSort.userRequested)
        legacyMergeSort(a);
    else
        ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}

/** To be removed in a future release. */
private static void legacyMergeSort(Object[] a) {
    Object[] aux = a.clone();
    mergeSort(aux, a, 0, a.length, 0);
}

版权声明

This site by Linest is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由Linest创作并维护的博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文永久链接：http://linest.github.io/2017/10/03/java-compare/