关于Comparable、Comparator接口返回值决定顺序的问题

Comparable和Comparator接口都是实现集合中元素的比较、排序的，下面先简单介绍下他们的用法。

1. 使用示例

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

        ArrayList<Person> list = new ArrayList<>();list.add(new Person("朱一百",100));list.add(new Person("朱八零",80));list.add(new Person("朱八一",81));list.add(new Person("朱九零",90));list.add(new Person("朱八二",82));list.add(new Person("朱七七",77));list.add(new Person("朱八八",88));list.add(new Person("朱重八",88));

1.1 Comparable

public class Person  implements Comparable<Person>{......@Overridepublic int compareTo(Person o) {if (this.getAge() < o.getAge()) {return -1;} else if (this.getAge() > o.getAge()) {return 1;} else {return this.getName().compareTo(o.getName());}}
}

public class ComparableTest {public static void main(String[] args) {......Collections.sort(list);list.forEach(System.out::println);}
}

1.2 Comparator

public class PersonComparator  implements Comparator<Person> {@Overridepublic int compare(Person o1, Person o2) {if (o1.getAge() < o2.getAge()) {return -1;} else if (o1.getAge() > o2.getAge()) {return 1;} else {return o1.getName().compareTo(o2.getName());}}
}

public class ComparatorTest {public static void main(String[] args) {......Collections.sort(list,new PersonComparator());list.forEach(System.out::println);}
}

以上的两个例子输出的结果如下所示：

Person{name='朱七七', age=77}
Person{name='朱八零', age=80}
Person{name='朱八一', age=81}
Person{name='朱八二', age=82}
Person{name='朱八八', age=88}
Person{name='朱啊八', age=88}
Person{name='朱九零', age=90}
Person{name='朱一百', age=100}

按照年龄升序排列，年龄相同时按照姓名升序排序。

2. 关于返回结果-1 0 1 和排序的关系

在上面的例子中我们分别实现了compare() 和compareTo()对集合继续宁排序，但是我们想知道方法返回-1、0、1对集合排序的关系。

2.1 Comparable

List#sort() =>ArrayList#sort() => Arrays#sort() ⇒ ComparableTimSort#sort() ⇒ ComparableTimSort.#countRunAndMakeAscending()

可以看到到Comparator c == null 时进入sort() 方法，当我们实现Comparator进行排序时，进入的方法就应该是 TimSort.sort()



countRunAndMakeAscending方法如下：

    private static int countRunAndMakeAscending(Object[] a, int lo, int hi) {assert lo < hi;int runHi = lo + 1;if (runHi == hi)return 1;if (((Comparable) a[runHi++]).compareTo(a[lo]) < 0) { // Descendingwhile (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) < 0)runHi++;reverseRange(a, lo, runHi);} else {                              // Ascendingwhile (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) >= 0)runHi++;}return runHi - lo;}

如果当前子序列是"递减"的，也就是 a[runHi] 小于 a[lo]，那么需要找到连续"递减"的子序列的结束位置 runHi。直到找到第一个不满足"递减"条件的元素。然后，调用 reverseRange 方法将"递减"的子序列反转为"递增"的子序列。

如果当前子序列是"递增"的，也就是 a[runHi] 大于等于 a[lo]，那么需要找到连续"递增"的子序列的结束位置 runHi。
最后，返回 runHi - lo，即子序列的长度。

    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++) {Comparable pivot = (Comparable) a[start];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;// pivot元素的索引比a[mid]的索引大// pivot元素在数组中比a[mid]靠后if (pivot.compareTo(a[mid]) < 0)right = mid;elseleft = mid + 1;}assert left == right;int n = start - left;  // The number of elements to move// Switch is just an optimization for arraycopy in default caseswitch (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;}}

这个方法做的事情如下：

1. 经过countRunAndMakeAscending()方法 start位置之前的集合是有序的，于是start位置开始，pivot=array[start]，使用二分查找法对start之前已经有序的数组比对，从start下标开始从后往前找，找到start下标之前第一个大于array[start]的元素下标index；
2. 根据要移动的步数n = start - left做了优化，但是目的是将[left, start-1]范围内的数组值都向后移动一位，放在 [left+1~start]，再把pivot的值赋予array[left]；
3. start++，循环执行以上步骤直到数组结束

总结

我们实现的compareTo()方法返回-1 0 1 和集合的排序是升序或者降序没有直接的关系，在上面的方法我们可以看到的是compareTo()返回会导致如下结果：

1. 返回-1说明两个比较的元素需要交换位置
2. 但会0或者1不需要交换两个元素的位置

所以我们应该能比较清楚的知道返回-1 0 1 给我们排序带来的效果了，比如上方的pivot.compareTo(a[mid]) pivot在数组中比a[mid]靠后，当 if (this.getAge() < o.getAge()) {return -1}; 我们希望pivot的age小于a[mid]时交换位置，最后排序的结果就是年龄的升序，如果if (this.getAge() < o.getAge()) {return 1};最后排序的结果就是年龄的降序