面试题：Java集合框架下自定义对象复杂比较及性能优化

Book类定义

public class Book {
    private String title;
    private String author;
    private double price;
    private int publishYear;

    public Book(String title, String author, double price, int publishYear) {
        this.title = title;
        this.author = author;
        this.price = price;
        this.publishYear = publishYear;
    }

    public String getTitle() {
        return title;
    }

    public String getAuthor() {
        return author;
    }

    public double getPrice() {
        return price;
    }

    public int getPublishYear() {
        return publishYear;
    }
}

排序实现

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

public class BookSorter {
    public static void main(String[] args) {
        List<Book> books = new ArrayList<>();
        books.add(new Book("Book1", "Author2", 20.0, 2020));
        books.add(new Book("Book2", "Author1", 15.0, 2019));
        books.add(new Book("Book3", "Author2", 25.0, 2018));

        Collections.sort(books, new BookComparator());

        for (Book book : books) {
            System.out.println("Title: " + book.getTitle() + ", Author: " + book.getAuthor() + ", Publish Year: " + book.getPublishYear());
        }
    }

    static class BookComparator implements Comparator<Book> {
        @Override
        public int compare(Book b1, Book b2) {
            int authorComparison = b1.getAuthor().compareTo(b2.getAuthor());
            if (authorComparison != 0) {
                return authorComparison;
            } else {
                return Integer.compare(b2.getPublishYear(), b1.getPublishYear());
            }
        }
    }
}

性能瓶颈分析
- 时间复杂度：使用Collections.sort方法，其底层通常是归并排序或快速排序（在Java 8及以上，ArrayList的sort方法默认使用TimSort），平均时间复杂度为O(n log n)，其中n是ArrayList中元素的数量。对于大量数据，这个时间复杂度虽然已经比较高效，但随着数据量的急剧增加，排序时间仍然会显著增长。
- 空间复杂度：如果使用归并排序，在排序过程中需要额外的空间来进行合并操作，空间复杂度为O(n)。这对于大量数据来说，可能会导致内存压力增大。
优化方案
- 并行排序：在Java 8及以上，可以使用Arrays.parallelSort或Collection的并行流进行排序。例如：

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.stream.Collectors;

public class ParallelBookSorter {
    public static void main(String[] args) {
        List<Book> books = new ArrayList<>();
        // 初始化大量数据

        List<Book> sortedBooks = books.parallelStream()
              .sorted(new BookComparator())
              .collect(Collectors.toList());

        for (Book book : sortedBooks) {
            System.out.println("Title: " + book.getTitle() + ", Author: " + book.getAuthor() + ", Publish Year: " + book.getPublishYear());
        }
    }

    static class BookComparator implements java.util.Comparator<Book> {
        @Override
        public int compare(Book b1, Book b2) {
            int authorComparison = b1.getAuthor().compareTo(b2.getAuthor());
            if (authorComparison != 0) {
                return authorComparison;
            } else {
                return Integer.compare(b2.getPublishYear(), b1.getPublishYear());
            }
        }
    }
}

外部排序：如果数据量过大，内存无法容纳，可以使用外部排序算法。例如，将数据分块读入内存，分别排序后再合并。可以使用Java的BufferedReader和BufferedWriter等流操作实现。这需要额外处理数据分块、临时文件管理等问题，但可以处理远超内存容量的数据量。

星途面试题库

面试题：Java集合框架下自定义对象复杂比较及性能优化

知识考点

面试题答案