Comparable 与 Comparator的区别
Comparable & Comparator 都是用来实现集合中元素的比较、排序的，只是 Comparable 是在集合内部定义的方法实现的排序，Comparator 是在集合外部实现的排序，所以，如想实现排序，就需要在集合外定义 Comparator 接口的方法或在集合内实现 Comparable 接口的方法。
Comparator位于包java.util下，而Comparable位于包 java.lang下 Comparable 是一个对象本身就已经支持自比较所需要实现的接口（如 String、Integer 自己就可以完成比较大小操作，已经实现了Comparable接口） 自定义的类要在加入list容器中后能够排序，可以实现Comparable接口，在用Collections类的sort方法排序时，如果不指定Comparator，那么就以自然顺序排序， 这里的自然顺序就是实现Comparable接口设定的排序方式。
而 Comparator 是一个专用的比较器，当这个对象不支持自比较或者自比较函数不能满足你的要求时，你可以写一个比较器来完成两个对象之间大小的比较。 可以说一个是自已完成比较，一个是外部程序实现比较的差别而已。 用 Comparator 是策略模式（strategy design pattern），就是不改变对象自身，而用一个策略对象（strategy object）来改变它的行为。 比如：你想对整数采用绝对值大小来排序，Integer 是不符合要求的，你不需要去修改 Integer 类（实际上你也不能这么做）去改变它的排序行为，只要使用一个实现了 Comparator 接口的对象来实现控制它的排序就行了。
小结：Comparatable接口必须由需要排序的多元素类本身来实现，且在其内部重写comparaTo()方法；Comparator接口是在需要排序的多元素类的外部（即使用外部类）来实现，且必须在该外部类中重写compara()方法。
两者的比较
- comparable接口：
- 优点：对于单元素集合可以实现直接排序
- 缺点：对于多元素排序，排序依据是固定不可更改的。（元素内部只能实现一次compareTo方法）
- 元素的排序依据时刻变的，所以可以通过定义多个外部类的方式来实现不同的排序。使用时按照需求选取。
- 创建外部类的代价太大。
- comparator接口：
实例：
1、实现Comparable接口（类内部实现比较函数）
需要比较的实体类：
1 public class Student implements Comparable<Student> { 2 3 private String name; 4 private int age; 5 6 public Student(String name, int age){ 7 this.name = name; 8 this.age = age; 9 } 10 11 public String getName() { 12 return name; 13 } 14 15 public void setName(String name) { 16 this.name = name; 17 } 18 19 public int getAge() { 20 return age; 21 } 22 23 public void setAge(int age) { 24 this.age = age; 25 } 26 27 28 @Override//类内部实现比较，因此在数组比较时只要传递一个对象数组 29 public int compareTo(Student o) { 30 return this.name.compareTo(o.name); 31 } 32 33 34 public String toString(){ 35 return "Student name ="+name+" age = "+age; 36 } 37 38 }
执行排序：
1 import java.util.Arrays; 2 3 public class RunComparable { 4 5 public static void main(String args[]){ 6 Student stu[] = new Student[5]; 7 stu[0] = new Student("hoojjack",20); 8 stu[1] = new Student("hoojj",24); 9 stu[2] = new Student("oojjack",19); 10 stu[3] = new Student("jjack",21); 11 stu[4] = new Student("ack",28); 12 for(int i=0;i<stu.length;i++) 13 System.out.println(stu[i].toString()); 14 System.out.println("---------------"); 15 Arrays.sort(stu); 16 for(int i=0;i<stu.length;i++) 17 System.out.println(stu[i].toString()); 18 } 19 20 21 }
结果：
1 //以name排序 2 Student name =hoojjack age = 20 3 Student name =hoojj age = 24 4 Student name =oojjack age = 19 5 Student name =jjack age = 21 6 Student name =ack age = 28 7 --------------- 8 Student name =ack age = 28 9 Student name =hoojj age = 24 10 Student name =hoojjack age = 20 11 Student name =jjack age = 21 12 Student name =oojjack age = 19
2、实现Comparator接口（需要自己单独新建一个类来写比较方法）
实体类:
1 public class Student { 2 3 private String name; 4 private int age; 5 6 public Student(String name, int age){ 7 this.name = name; 8 this.age = age; 9 } 10 11 public String getName() { 12 return name; 13 } 14 15 public void setName(String name) { 16 this.name = name; 17 } 18 19 public int getAge() { 20 return age; 21 } 22 23 public void setAge(int age) { 24 this.age = age; 25 } 26 27 public String toString(){ 28 return "Student name ="+name+" age = "+age; 29 }
单独实现的比较类需要继承Comparator类，以按年龄排序：
1 import java.util.Comparator; 2 3 public class StudentComparator implements Comparator<Student> { 4 5 @Override 6 public int compare(Student o1, Student o2) { 7 if(o1.getAge()>o2.getAge()) 8 return 1; 9 else if(o1.getAge()<o2.getAge()) 10 return -1; 11 else 12 return 0; 13 } 14 15 }
执行排序：
1 import java.util.Arrays; 2 3 public class RunComparable { 4 5 public static void main(String args[]){ 6 Student stu[] = new Student[5]; 7 stu[0] = new Student("hoojjack",20); 8 stu[1] = new Student("hoojj",24); 9 stu[2] = new Student("oojjack",19); 10 stu[3] = new Student("jjack",21); 11 stu[4] = new Student("ack",28); 12 for(int i=0;i<stu.length;i++) 13 System.out.println(stu[i].toString()); 14 System.out.println("---------------"); 15 Arrays.sort(stu,new StudentComparator());//唯一区别的地方 16 for(int i=0;i<stu.length;i++) 17 System.out.println(stu[i].toString()); 18 } 19 20 21 }
结果：
1 //按age排序 2 Student name =hoojjack age = 20 3 Student name =hoojj age = 24 4 Student name =oojjack age = 19 5 Student name =jjack age = 21 6 Student name =ack age = 28 7 --------------- 8 Student name =oojjack age = 19 9 Student name =hoojjack age = 20 10 Student name =jjack age = 21 11 Student name =hoojj age = 24 12 Student name =ack age = 28
Java源码中的Arrays实现方法：
1 //------1------ 2 public static <T> void sort(T[] a, Comparator<? super T> c) { 3 if (c == null) { 4 sort(a); 5 } else { 6 if (LegacyMergeSort.userRequested) 7 legacyMergeSort(a, c); 8 else 9 TimSort.sort(a, 0, a.length, c, null, 0, 0); 10 } 11 }
1 //-----2------- 2 public static <T> void sort(T[] a, int fromIndex, int toIndex, 3 Comparator<? super T> c) { 4 if (c == null) { 5 sort(a, fromIndex, toIndex); 6 } else { 7 rangeCheck(a.length, fromIndex, toIndex); 8 if (LegacyMergeSort.userRequested) 9 legacyMergeSort(a, fromIndex, toIndex, c); 10 else 11 TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0); 12 } 13 }
1 //------3------ 2 static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c, 3 T[] work, int workBase, int workLen) { 4 assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length; 5 6 int nRemaining = hi - lo; 7 if (nRemaining < 2) 8 return; // Arrays of size 0 and 1 are always sorted 9 10 // If array is small, do a "mini-TimSort" with no merges 11 if (nRemaining < MIN_MERGE) { 12 int initRunLen = countRunAndMakeAscending(a, lo, hi, c); 13 binarySort(a, lo, hi, lo + initRunLen, c); 14 return; 15 }
countRunAndMakeAscending函数如4、binarySort函数如5所示
1 //-------4-------- 2 private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi, 3 Comparator<? super T> c) { 4 assert lo < hi; 5 int runHi = lo + 1; 6 if (runHi == hi) 7 return 1; 8 9 // Find end of run, and reverse range if descending 10 if (c.compare(a[runHi++], a[lo]) < 0) { // Descending 11 while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0) 12 runHi++; 13 reverseRange(a, lo, runHi); 14 } else { // Ascending 15 while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0) 16 runHi++; 17 } 18 19 return runHi - lo; 20 }
1 //--------5------- 2 @SuppressWarnings("fallthrough") 3 private static <T> void binarySort(T[] a, int lo, int hi, int start, 4 Comparator<? super T> c) { 5 assert lo <= start && start <= hi; 6 if (start == lo) 7 start++; 8 for ( ; start < hi; start++) { 9 T pivot = a[start]; 10 11 // Set left (and right) to the index where a[start] (pivot) belongs 12 int left = lo; 13 int right = start; 14 assert left <= right; 15 /* 16 * Invariants: 17 * pivot >= all in [lo, left). 18 * pivot < all in [right, start). 19 */ 20 while (left < right) { 21 int mid = (left + right) >>> 1; 22 if (c.compare(pivot, a[mid]) < 0) 23 right = mid; 24 else 25 left = mid + 1; 26 } 27 assert left == right; 28 29 /* 30 * The invariants still hold: pivot >= all in [lo, left) and 31 * pivot < all in [left, start), so pivot belongs at left. Note 32 * that if there are elements equal to pivot, left points to the 33 * first slot after them -- that's why this sort is stable. 34 * Slide elements over to make room for pivot. 35 */ 36 int n = start - left; // The number of elements to move 37 // Switch is just an optimization for arraycopy in default case 38 switch (n) { 39 case 2: a[left + 2] = a[left + 1]; 40 case 1: a[left + 1] = a[left]; 41 break; 42 default: System.arraycopy(a, left, a, left + 1, n); 43 } 44 a[left] = pivot; 45 } 46 }