Java Comparable和Comparator

http://my.oschina.net/android520/blog/700738

public class ComparableUser implements Comparable<Object> {
	
	public String name;
	public int age;
	
	public ComparableUser(String name, int age) {
		this.name = name;
		this.age = age;
	}

	@Override
	public int compareTo(Object o) {
		return age - ((ComparableUser) o).age;
	}
}
ComparableUser[] users = new ComparableUser[] {
	new ComparableUser("Jim", 80),
	new ComparableUser("Tom", 10),
	new ComparableUser("Lily", 30),
	new ComparableUser("Marry", 20)
};
Arrays.sort(users);

Comparable接口，只要类继承该接口，就可以实现对象的排序功能。

public class User {
	public String name;
	public int age;
	public User(String name, int age) {
		this.name = name;
		this.age = age;
	}
}
public class ComparatorUser implements Comparator<User> {
	@Override
	public int compare(User o1, User o2) {
		return o1.age - o2.age;
	}
}
User[] users2 = new User[] {
	new User("Jim", 80),
	new User("Tom", 10),
	new User("Lily", 30),
	new User("Marry", 20)
};
Arrays.sort(users2, new ComparatorUser());

Comparator接口，可以用来对已有的未继承Comparable接口的，进行排序。



sort方法，在JDK6和JDK7中实现方式不一样，具体如下：

来自http://blog.sina.com.cn/s/blog_8e6f1b330101h7fa.html

在Java 6中Arrays.sort()和Collections.sort()使用的是MergeSort，而在Java 7中，内部实现换成了TimSort，其对对象间比较的实现要求更加严格：

Comparator的实现必须保证以下几点（出自这儿）：

a). sgn(compare(x, y)) == -sgn(compare(y, x))
b). (compare(x, y)>0) && (compare(y, z)>0) 意味着 compare(x, z)>0
c). compare(x, y)==0 意味着对于任意的z：sgn(compare(x, z))==sgn(compare(y, z)) 均成立

而我们的代码中，某个compare()实现片段是这样的：

public int compare(ComparatorTest o1, ComparatorTest o2) {
    return o1.getValue() > o2.getValue() ? 1 : -1;
}

这就违背了a)原则：假设X的value为1，Y的value也为1；那么compare(X, Y) ≠ –compare(Y, X)
PS: TimSort不仅内置在各种JDK 7的版本，也存在于Android SDK中（尽管其并没有使用JDK 7）。



下面看下sort方法中的具体排序源码

    static void sort(Object[] a, int lo, int hi) {
        rangeCheck(a.length, lo, hi);
        int nRemaining  = hi - lo;
        if (nRemaining < 2)
            return;  // Arrays of size 0 and 1 are always sorted

        // If array is small, do a "mini-TimSort" with no merges
        if (nRemaining < MIN_MERGE) {
            int initRunLen = countRunAndMakeAscending(a, lo, hi);
            binarySort(a, lo, hi, lo + initRunLen);
            return;
        }
        ............................
    }

从代码中可以看出使用的是二分法排序binarySort

/**
     * Sorts the specified portion of the specified array using a binary
     * insertion sort.  This is the best method for sorting small numbers
     * of elements.  It requires O(n log n) compares, but O(n^2) data
     * movement (worst case).
     *
     * If the initial part of the specified range is already sorted,
     * this method can take advantage of it: the method assumes that the
     * elements from index {@code lo}, inclusive, to {@code start},
     * exclusive are already sorted.
     *
     * @param a the array in which a range is to be sorted
     * @param lo the index of the first element in the range to be sorted
     * @param hi the index after the last element in the range to be sorted
     * @param start the index of the first element in the range that is
     *        not already known to be sorted ({@code lo <= start <= hi})
     */
    @SuppressWarnings("fallthrough")
    private static void binarySort(Object[] a, int lo, int hi, int start) {
        assert lo <= start && start <= hi;
        if (start == lo)
            start++;
        for ( ; start < hi; start++) {
            @SuppressWarnings("unchecked")
            Comparable<Object> pivot = (Comparable) a[start];

            // Set left (and right) to the index where a[start] (pivot) belongs
            int left = lo;
            int right = start;
            assert left <= right;
            /*
             * Invariants:
             *   pivot >= all in [lo, left).
             *   pivot <  all in [right, start).
             */
            while (left < right) {
                int mid = (left + right) >>> 1;
                if (pivot.compareTo(a[mid]) < 0)
                    right = mid;
                else
                    left = mid + 1;
            }
            assert left == right;

            /*
             * The invariants still hold: pivot >= all in [lo, left) and
             * pivot < all in [left, start), so pivot belongs at left.  Note
             * that if there are elements equal to pivot, left points to the
             * first slot after them -- that's why this sort is stable.
             * Slide elements over to make room for pivot.
             */
            int n = start - left;  // The number of elements to move
            // Switch is just an optimization for arraycopy in default case
            switch (n) {
                case 2:  a[left + 2] = a[left + 1];
                case 1:  a[left + 1] = a[left];
                         break;
                default: System.arraycopy(a, left, a, left + 1, n);
            }
            a[left] = pivot;
        }
    }