面试题：Java中Java Collections工具类的sort方法原理

Question

请简述Java Collections工具类中sort方法对List进行排序的基本原理。如果要对自定义对象的List进行排序，需要满足什么条件，如何实现？

Answer 1

Collections工具类中sort方法对List排序的基本原理

1. 对于实现了RandomAccess接口的List（如ArrayList）：
   • 使用TimSort算法。TimSort是一种稳定的排序算法，它结合了归并排序和插入排序的优点。
   • 它首先会将数组分成多个小的子数组（run），然后对这些子数组使用插入排序进行排序。
   • 接着将这些排好序的子数组合并起来，在合并过程中，它会利用已经部分有序的特点，减少比较和移动的次数，从而提高排序效率。
2. 对于没有实现RandomAccess接口的List（如LinkedList）：
   • 使用归并排序。归并排序是一种稳定的排序算法，它将一个列表递归地分成两半，分别对两半进行排序，然后将两个有序的子列表合并成一个有序的列表。
   • 对于链表结构，归并排序不需要随机访问的能力，并且其空间复杂度和时间复杂度相对稳定，所以适用于链表这种不支持快速随机访问的数据结构。

对自定义对象的List进行排序需满足的条件及实现方式

1. 实现Comparable接口：
   • 条件：自定义类需要实现Comparable接口，该接口定义了一个compareTo方法。
   • 实现方式：在自定义类中重写compareTo方法，在该方法中定义比较逻辑。例如：

class CustomObject implements Comparable<CustomObject> {
    private int value;
    public CustomObject(int value) {
        this.value = value;
    }
    @Override
    public int compareTo(CustomObject other) {
        // 按value从小到大排序
        return Integer.compare(this.value, other.value);
    }
}

然后可以直接使用Collections.sort(listOfCustomObjects)对包含CustomObject的列表进行排序。 2. 使用Comparator接口：

• 条件：定义一个实现了Comparator接口的类或使用匿名内部类、Lambda表达式来创建Comparator实例。
• 实现方式：
  • 实现Comparator接口类：

class CustomObjectComparator implements Comparator<CustomObject> {
    @Override
    public int compare(CustomObject o1, CustomObject o2) {
        return Integer.compare(o1.getValue(), o2.getValue());
    }
}

然后使用Collections.sort(listOfCustomObjects, new CustomObjectComparator());对列表排序。 - 匿名内部类：

Collections.sort(listOfCustomObjects, new Comparator<CustomObject>() {
    @Override
    public int compare(CustomObject o1, CustomObject o2) {
        return Integer.compare(o1.getValue(), o2.getValue());
    }
});

 - **Lambda表达式**：

Collections.sort(listOfCustomObjects, (o1, o2) -> Integer.compare(o1.getValue(), o2.getValue()));