面试题：Java中Collections工具类如何对List进行排序

代码示例：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class CustomClass implements Comparable<CustomClass> {
    private int value;

    public CustomClass(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    @Override
    public int compareTo(CustomClass other) {
        return Integer.compare(this.value, other.value);
    }
}

public class Main {
    public static void main(String[] args) {
        List<CustomClass> list = new ArrayList<>();
        list.add(new CustomClass(3));
        list.add(new CustomClass(1));
        list.add(new CustomClass(2));

        Collections.sort(list);

        for (CustomClass obj : list) {
            System.out.println(obj.getValue());
        }
    }
}

排序原理：
- 当自定义类实现了Comparable接口，就定义了该类对象之间的自然顺序。Comparable接口中有一个compareTo方法，该方法用于定义两个对象比较的逻辑。在上述示例中，CustomClass类的compareTo方法根据value字段定义了比较逻辑，这里是按照value的升序排序。
- 排序算法基于比较排序的基本思想，通过不断比较元素之间的大小关系，将元素按照定义好的顺序重新排列。
Collections.sort()方法的工作机制：
- Collections.sort(List<T> list)方法内部采用了一种优化的排序算法，在JDK 7及之后版本，Collections.sort对于RandomAccess类型的List（如ArrayList）使用TimSort算法，对于其他类型的List（如LinkedList）使用MergeSort算法。
- TimSort算法：它是一种稳定的、自适应的、混合的归并排序算法。它结合了插入排序和归并排序的优点，在数据部分有序时利用插入排序的高效性，对于完全无序的数据使用归并排序。它首先将数据分解成多个小的有序块（run），然后通过归并操作将这些有序块合并成一个完整的有序列表。
- MergeSort算法：归并排序是一种分治算法，将一个列表分成两个子列表，对每个子列表递归地进行排序，然后将两个有序的子列表合并成一个有序的列表。在合并过程中，比较两个子列表的元素，将较小（或按照compareTo方法定义的顺序）的元素先放入结果列表，直到所有元素都合并完成。

星途面试题库

面试题：Java中Collections工具类如何对List进行排序

知识考点

面试题答案