前言

最近笔者被问到对象排序的时候，要求是传入不同的规则，排序不一样，类似一个按不同的条件排序的功能，笔者想到了comparator，其实comparable也是可以的，只是不太符合这个功能而已，通过comparator的切换即可实现。

comparable

comparable demo

comparable是一个接口，使用的bean实现即可，非常方便，缺点是与bean强藕联。

public class User implements Comparable<User>{private String name;private int age;public String getName() {return name;}public void setName(String name) {this.name = name;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}@Overridepublic int compareTo(User o) {return o.getAge() - this.getAge();}@Overridepublic String toString() {return "User{" +"name='" + name + '\'' +", age=" + age +'}';}
}

实现compareTo方法，一个对象是比较的其他对象，一个是对象本身，使用符号位判断大小，即0与正负数。此示例表示按照User的age倒序排列，示例如下：

public static void main(String[] args) {List<User> users = new ArrayList<>();User user1 = new User();user1.setAge(11);User user2 = new User();user2.setAge(22);users.add(user1);users.add(user2);Collections.sort(users);System.out.println(users);}

结果如下：

comparable源码分析

Collections.sort，以list的排序为例，本身是一个静态方法，T泛型限制必须实现Comparable接口。

public static <T extends Comparable<? super T>> void sort(List<T> list) {list.sort(null);}

调用的list的sort方法，笔者是ArrayList，估计其他实现略有区别

public void sort(Comparator<? super E> c) {final int expectedModCount = modCount;Arrays.sort((E[]) elementData, 0, size, c);if (modCount != expectedModCount) {throw new ConcurrentModificationException();}modCount++;}

调用Arrays.sort((E[]) elementData, 0, size, c);

ComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0);

TimSort排序，双轴快排，这里就比较复杂了

static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) {assert a != null && lo >= 0 && lo <= hi && hi <= a.length;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 mergesif (nRemaining < MIN_MERGE) {int initRunLen = countRunAndMakeAscending(a, lo, hi);binarySort(a, lo, hi, lo + initRunLen);return;}/*** March over the array once, left to right, finding natural runs,* extending short natural runs to minRun elements, and merging runs* to maintain stack invariant.*/ComparableTimSort ts = new ComparableTimSort(a, work, workBase, workLen);int minRun = minRunLength(nRemaining);do {// Identify next runint runLen = countRunAndMakeAscending(a, lo, hi);// If run is short, extend to min(minRun, nRemaining)if (runLen < minRun) {int force = nRemaining <= minRun ? nRemaining : minRun;binarySort(a, lo, lo + force, lo + runLen);runLen = force;}// Push run onto pending-run stack, and maybe mergets.pushRun(lo, runLen);ts.mergeCollapse();// Advance to find next runlo += runLen;nRemaining -= runLen;} while (nRemaining != 0);// Merge all remaining runs to complete sortassert lo == hi;ts.mergeForceCollapse();assert ts.stackSize == 1;}

按照32的mini-TimSort划分，无需merges，超过的需要二分查找插入排序。这里就涉及真正的算法了，如果其他实现，可能不是这样的。

comparator

comparator demo

comparator是函数式接口，只有一个实现方法，基于比较接口，好处是，可以动态的更换接口的多个实现。

public static void main(String[] args) {List<User> users = new ArrayList<>();User user1 = new User();user1.setAge(11);User user2 = new User();user2.setAge(22);users.add(user1);users.add(user2);
//        Collections.sort(users);Collections.sort(users, new MyCompare());System.out.println(users);}private static class MyCompare implements Comparator<User> {@Overridepublic int compare(User o1, User o2) {return o2.getAge() - o1.getAge();}}

运行结果同理

但是我们可以写多个实现接口的类。

Comparator源码分析

函数式接口，很明显的定义

@FunctionalInterface
public interface Comparator<T> {

sort方法，当然这个是集合工具类，我们可以自己实现排序外的逻辑

public static <T> void sort(List<T> list, Comparator<? super T> c) {list.sort(c);}

仍然

Arrays.sort((E[]) elementData, 0, size, c);

但是这里c是有比较器的，意味着使用比较器来比较

TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);

TimSort排序

static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,T[] work, int workBase, int workLen) {assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length;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 mergesif (nRemaining < MIN_MERGE) {int initRunLen = countRunAndMakeAscending(a, lo, hi, c);binarySort(a, lo, hi, lo + initRunLen, c);return;}/*** March over the array once, left to right, finding natural runs,* extending short natural runs to minRun elements, and merging runs* to maintain stack invariant.*/TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen);int minRun = minRunLength(nRemaining);do {// Identify next runint runLen = countRunAndMakeAscending(a, lo, hi, c);// If run is short, extend to min(minRun, nRemaining)if (runLen < minRun) {int force = nRemaining <= minRun ? nRemaining : minRun;binarySort(a, lo, lo + force, lo + runLen, c);runLen = force;}// Push run onto pending-run stack, and maybe mergets.pushRun(lo, runLen);ts.mergeCollapse();// Advance to find next runlo += runLen;nRemaining -= runLen;} while (nRemaining != 0);// Merge all remaining runs to complete sortassert lo == hi;ts.mergeForceCollapse();assert ts.stackSize == 1;}

算法类似，只是new TimSort<>(a, c, work, workBase, workLen);，传入了比较器

总结

其实很简单的比较，推荐comparator，函数式编程，更灵活。这里的比较算法使用的Arrays.sort非常复杂的算法，Arrays还可以并行排序，估计效率更高

public static <T> void parallelSort(T[] a, int fromIndex, int toIndex,Comparator<? super T> cmp) {rangeCheck(a.length, fromIndex, toIndex);if (cmp == null)cmp = NaturalOrder.INSTANCE;int n = toIndex - fromIndex, p, g;if (n <= MIN_ARRAY_SORT_GRAN ||(p = ForkJoinPool.getCommonPoolParallelism()) == 1)TimSort.sort(a, fromIndex, toIndex, cmp, null, 0, 0);elsenew ArraysParallelSortHelpers.FJObject.Sorter<T>(null, a,(T[])Array.newInstance(a.getClass().getComponentType(), n),fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?MIN_ARRAY_SORT_GRAN : g, cmp).invoke();}

可以看出小于1 << 13，即8192，还是原来的做法，多了才会并行排序。

另外Collections还可以sortedMap