面试题：Java Collections工具类自定义排序与性能优化策略

代码实现

假设复杂对象为ComplexObject，包含属性attr1和attr2，以下是使用Collections工具类和自定义Comparator实现排序的代码：

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

class ComplexObject {
    private int attr1;
    private int attr2;

    public ComplexObject(int attr1, int attr2) {
        this.attr1 = attr1;
        this.attr2 = attr2;
    }

    public int getAttr1() {
        return attr1;
    }

    public int getAttr2() {
        return attr2;
    }
}

public class SortComplexObject {
    public static void main(String[] args) {
        List<ComplexObject> list = new ArrayList<>();
        list.add(new ComplexObject(3, 5));
        list.add(new ComplexObject(1, 7));
        list.add(new ComplexObject(3, 2));

        Collections.sort(list, new CustomComparator());

        for (ComplexObject obj : list) {
            System.out.println("attr1: " + obj.getAttr1() + ", attr2: " + obj.getAttr2());
        }
    }

    static class CustomComparator implements Comparator<ComplexObject> {
        @Override
        public int compare(ComplexObject o1, ComplexObject o2) {
            int result = Integer.compare(o1.getAttr1(), o2.getAttr1());
            if (result == 0) {
                return Integer.compare(o1.getAttr2(), o2.getAttr2());
            }
            return result;
        }
    }
}

时间复杂度分析

在Java中，Collections.sort方法（对于ArrayList）通常使用的是TimSort算法。TimSort算法的时间复杂度是O(n log n)，其中n是集合中元素的数量。这是因为它结合了归并排序和插入排序的优点，在最坏、平均和最好情况下都能保证接近O(n log n)的性能。

空间复杂度分析

TimSort算法的空间复杂度在最坏情况下是O(n)，因为在合并过程中可能需要额外的空间来存储临时数据。然而，在实际应用中，由于它会利用已有的有序子序列，空间复杂度通常会更接近O(log n)。

优化排序性能的策略

减少比较次数：如果对象的某些属性在大部分情况下已经是有序的，可以先对这些属性进行预排序，然后再对其他属性进行排序。这样可以减少后续比较的次数。
并行排序：对于Java 8及以上版本，可以使用Arrays.parallelSort或Stream.sorted方法，这些方法会利用多核处理器进行并行排序，在数据量较大时能显著提高排序性能。
使用更高效的数据结构：如果数据量非常大且需要频繁进行排序操作，可以考虑使用更适合排序的数据结构，如平衡二叉搜索树（如TreeSet）。但要注意这种数据结构在插入和删除操作上的性能开销。
减少对象创建：在自定义Comparator中，如果每次比较都创建新的对象（例如使用new Integer()进行包装），可以改为使用Integer.compare这样的静态方法，避免不必要的对象创建，从而提高性能。

星途面试题库

面试题：Java Collections工具类自定义排序与性能优化策略

知识考点

面试题答案

代码实现

时间复杂度分析

空间复杂度分析

优化排序性能的策略