【java】排序相关

骑猪看日落 2024-03-16 19:51 16阅读 0赞

### 排序的稳定性指什么 ###

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，A1=A2，且A1在A2之前，而在排序后的序列中，A1仍在A2之前，则称这种排序算法是稳定的；否则称为不稳定的。

### Java的内置排序用的是什么排序 ###

Java中自带了两种排序方法， 一种是 Collections.sort()， 另一种是 Arrays.sort()。而Collections.sort方法底层就是调用的array.sort方法

那么看一下sort方法：

对于基本数据类型的数组，假设数组长度为length：

1.  如果length<47，那么采用插入排序算法。
2.  如果47<=length<286，或者286<=length，但数组不具备特定结构，那么使用快速排序的一种优化形式：双轴快排算法。
3.  如果286<=length，并且数组具备特定结构，那么使用归并排序算法。
    
     *  判断数组具不具备结构：实际逻辑是分组排序，每个降序序列为一个组，像1,9,8,7,6,8。9到6是降序，为一个组，然后把降序的一组排成升序：1,6,7,8,9,8。然后再从最后的8开始继续往后面找。
        
        每遇到这样一个降序组，++count，当count大于MAX\_RUN\_COUNT(67)，被判断为这个数组不具备结构，也就是说这数据时而升时而降，波峰波谷太多，排列太过陡峭，说明不适合采用归并排序，还是使用快速排序为宜。

### 堆排、快排、归并排分别用在什么场景 ###

用快排

*  当对于数据量大，数据分布高度随机的场景，快速排序的平均效率要高于 堆排序和 归并排序；

用堆排

*  对于Top- K问题，堆排序性能的下限(时间复杂度O(nlogn)要高于快排；
 *  另外一个适合用heap的场合是优先队列，需要在一组不停更新的数据中不停地找最大/小元素，快速排序也不合适。
 *  堆排序适合于数据量非常大的场合（百万数据）。  
    堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。

归并排序

*  归并排序适合链表排序但不适合数组排序；归并在外部排序，比如磁盘文件的情况下比快排好，因为快排很依赖数据的随机存取，而归并是顺序存取，对磁盘这种外存比较友好

冒泡排序

*  是否为原地排序：冒泡操作是在原数组之上进行的，只需要常量级的临时空间用于交换，空间复杂度为O ( 1 ) ，是原地排序算法。
 *  平均时间复杂度：冒泡排序交换数组的逆序对个数一样，而比较操作为k\*n次，
 *  何时时间复杂度最低：所需排序的数组是有序的，只需一次冒泡操作，其时间复杂度为O ( n ) 。
 *  何时时间复杂度最高：所需排序的数组是倒序排列的，需要n次冒泡操作，其时间复杂度为O(n^2)

### Comparator与Comparable有什么区别？ ###

*  Comparable & Comparator 都可以实现集合中元素排序
 *  Comparable 接口
    
     *  Comparable 位于包 java.lang 下
     *  若一个类实现了Comparable接口，就意味着该类支持排序。实现了Comparable接口的类，其对象存入列表或数组，可以通过 Collections.sort 或 Arrays.sort 进行自然排序。
     *  此外，实现此接口的对象可以用作有序映射中的键或有序集合中的集合，无需再指定比较器
     *  Comparable 接口只有一个方法compareTo()，子类实现接口，重写compareTo()，即可实现比较与排序
 *  Comparator 接口
    
     *  Comparator 位于包 java.util 下
     *  Comparator 本质上就是一个比较器，如果一个类本身没有实现Comparable接口，即不支持排序，那么我们就可以额外建立一个 第三方比较器 来进行排序
     *  这个 第三方比较器 需要实现Comparator接口，实现Comparator接口的方法：
        
         *  int compare(T o1, T o2)
         *  返回 正数，表示 o1 > o2；返回0，表示 o1 == o2；返回 负数，表示 o1 < o2
     *  然后就可以在 Arrays.sort 等比较方法中，传入第三方比较器对象。
     *  使用示例：
        
            // 1、有一个类Person，没有实现Comparable接口，即不支持排序
            public class Person
            {
                    
                public String name;
                public int age;
                public Person(String name, int age)
                {
                    
                    this.name = name;
                    this.age = age;
                }
            }
            
            // 2、现在想要对Person进行排序或比较，就需要定义一个 第三方比较器类
            // 该类实现Comparator接口，泛型传入Person，并重写compare()
            public class PersonCompartor implements Comparator<Person>
            {
                    
                @Override
                public int compare(Person o1, Person o2)
                {
                    
                    return o1.getAge()-o2.getAge();
                }
            }
            
            // 3、使用的时候，为Arrays.sort()第二个参数传入我们自定义的比较器
            public static void main(String[] args)
            {
                    
                Person[] people=new Person[]{
                    
                    new Person("xujian", 20),
                    new Person("xiewei", 10)
                };
                // 第二个参数，创建一个 自定义比较器对象 传入
                Arrays.sort(people, new PersonCompartor());
            }
 *  Comparable 与 Comparator 最大的区别：
    
     *  Comparable 是在 类源码 内部完成 接口的实现，方法的重写，这样这个类直接就支持排序了
     *  Comparator 是在 类外部 实现比较和排序，定义第三方比较器，可以弥补某些不支持排序的类的不足。
        
         *  当然，如果一个类 实现的 Comparable 不能满足我们的要求，也可以通过 Comparator 自定义第三方比较器 完成我们的需求。

### List根据集合内对象的某个属性进行排序 ###

//按照List中对象的id属性升序
    list.sort(Comparator.comparing(Stu::getId))
    
    //按照List中对象的id属性降序
    list.sort(Comparator.comparing(Stu::getId).reversed());
    
    //多条件升序
    list.sort(Comparator.comparing(Stu::getId).thenComparing(Stu::getSid));
    
    //id降序
    list.sort(Comparator.comparing(Stu::getId).reversed().thenComparing(Stu::getSid))