Comparable与Comparator排序对比

分手后的思念是犯贱 2022-10-19 13:00 202阅读 0赞

### Comparable ###

接口，一般是采取实现类接口compareTo方法的方式来达到内部排序的目的。也就这一个方法，一般也叫做自然排序，也就是实现了就只能按照这个排序规则，不能随意更改排序规则。  
例子：

public class Book implements Comparable<Object> { // 定义名为Book的类，默认继承自Object类  
            public int id;// 编号    
          
            public int compareTo(Object obj) {// Comparable接口中的方法  
                Book b = (Book) obj;  
                return this.id - b.id; // 按书的id比较大小，用于默认排序  
            }

### Comparator ###

也是接口类，但它可以帮助没有实现该接口的类来排序，主要是实现compare方法，这个是外部类，可以自由编写排序规则，每次都不同，不受约束。例子：

class StudentComparator implements Comparator<Student01>{    // 实现比较器
        // 因为Object类中本身已经有了equals()方法
        public int compare(Student01 s1,Student01 s2){
            if(s1.equals(s2)){
                return 0 ;
            }else if(s1.getAge()<s2.getAge()){    // 按年龄比较
                return 1 ;
            }else{
                return -1 ;
            }
        }
    };
    
    public class Comparator01{
        public static void main(String args[]){
            Student01 stu[] = {new Student01("张三",20),
                new Student01("李四",22),new Student01("王五",20),
                new Student01("赵六",20),new Student01("孙七",22)} ;
            java.util.Arrays.sort(stu,new StudentComparator()) ;    // 进行排序操作
            for(int i=0;i<stu.length;i++){    // 循环输出数组中的内容
                System.out.println(stu[i]) ;
            }
        }
    };

上述是比较复杂的写法，其实可以采用lambda表达式来实现：

Collections.sort(stu, new Comparator<Student01>() {
                public int compare(Student01 s1,Student01 s2){
            if(s1.equals(s2)){
                return 0 ;
            }else if(s1.getAge()<s2.getAge()){    // 按年龄比较
                return 1 ;
            }else{
                return -1 ;
            }
        }
            });

### Java实际使用的一些排序逻辑 ###

以上是分析了两种不同的排序方式，我们来看看实际排序情况，list中很多方法

*  Comparable 采取的是ComparableTimSort.sort排序算法  
    好像和下面的算法一样。
 *  Comparator 采取的是TimSort.sort排序算法  
    TimSort是结合了插入排序和归并排序稳定的排序算法，并做了许多优化，其中插入排序的逻辑是将排好序的数组之后的一个元素不停的向前移动交换元素直到找到合适的位置，如果这个新元素比前面的序列的最小的元素还要小，就要和前面的每个元素进行比较，浪费大量的时间在比较上面。采用二分搜索的方法直接找到这个元素应该插入的位置，就可以减少很多次的比较。虽然仍然是需要移动相同数量的元素，但是复制数组的时间消耗要小于元素间的一一互换。

### 时间复杂度 ###

归并排序已经到达了最坏情况下，比较排序算法时间复杂度的下界，所以在最坏的情况下，Timsort 时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn)。在最佳情况下，即输入已经排好序，它则以线性时间运行O ( n ) O(n)O(n)。可以看出Timsort是目前最好的排序方式。

### 参考博客 ###

[世界上最快的排序算法——Timsort][Timsort]  
[python中的sort之timsort学习][python_sort_timsort]

[Timsort]: https://www.cnblogs.com/sunshuyi/p/12680918.html
[python_sort_timsort]: https://zhuanlan.zhihu.com/p/158972725