手机网站管理,网站权重和什么有关,上海建设网站的价格,西安网站建设制作Comparable和Comparator接口都是实现集合中元素的比较、排序的#xff0c;下面先简单介绍下他们的用法。
1. 使用示例
public class Person {private String name;private Integer age;public Person() {}public Person(String name, Integer age) {this.name name;this.ag…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;}
}ArrayListPerson 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 ComparablePerson{......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 ComparatorPerson {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朱七七, age77}
Person{name朱八零, age80}
Person{name朱八一, age81}
Person{name朱八二, age82}
Person{name朱八八, age88}
Person{name朱啊八, age88}
Person{name朱九零, age90}
Person{name朱一百, age100}按照年龄升序排列年龄相同时按照姓名升序排序。
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;}}
这个方法做的事情如下
经过countRunAndMakeAscending()方法 start位置之前的集合是有序的于是start位置开始pivotarray[start]使用二分查找法对start之前已经有序的数组比对从start下标开始从后往前找找到start下标之前第一个大于array[start]的元素下标index根据要移动的步数n start - left做了优化但是目的是将[left, start-1]范围内的数组值都向后移动一位放在 [left1~start]再把pivot的值赋予array[left]start循环执行以上步骤直到数组结束
总结
我们实现的compareTo()方法返回-1 0 1 和集合的排序是升序或者降序没有直接的关系在上面的方法我们可以看到的是compareTo()返回会导致如下结果
返回-1说明两个比较的元素需要交换位置但会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};最后排序的结果就是年龄的降序
