第四章：集合框架

4.5 集合的排序与搜索

4.5.1 集合排序

在Java中，对集合进行排序是常见的操作。Java提供了多种方式来实现集合的排序：

  1. 自然排序（Comparable接口）
    如果集合中的元素实现了Comparable接口，可以直接使用Collections.sort()方法进行排序。例如：

    List<String> list = Arrays.asList("banana", "apple", "cherry");
Collections.sort(list); // 默认按字典序排序
System.out.println(list); // 输出: [apple, banana, cherry]

  2. 自定义排序（Comparator接口）
    如果需要对未实现Comparable接口的类进行排序，或者需要自定义排序规则，可以使用Comparator接口。例如：

    List<String> list = Arrays.asList("banana", "apple", "cherry");
Collections.sort(list, (s1, s2) -> s1.length() - s2.length()); // 按字符串长度排序
System.out.println(list); // 输出: [apple, banana, cherry]

  3. Java 8的Stream API排序
    使用Stream API可以更灵活地实现排序：

    List<String> sortedList = list.stream()
    .sorted(Comparator.reverseOrder()) // 逆序排序
    .collect(Collectors.toList());

4.5.2 集合搜索

在集合中搜索元素可以通过以下方式实现：

  1. 线性搜索
    对于未排序的集合，可以使用List.contains()或遍历集合进行搜索：

    List<Integer> numbers = Arrays.asList(3, 1, 4, 1, 5, 9);
boolean containsFive = numbers.contains(5); // true

  2. 二分搜索（Binary Search）
    对于已排序的集合，可以使用Collections.binarySearch()提高搜索效率：

    List<Integer> sortedNumbers = Arrays.asList(1, 3, 5, 7, 9);
int index = Collections.binarySearch(sortedNumbers, 5); // 返回索引2

  3. 使用Stream API过滤
    结合Stream API可以更灵活地实现条件搜索：

    Optional<Integer> result = numbers.stream()
    .filter(n -> n > 5)
    .findFirst(); // 返回第一个大于5的元素

4.5.3 性能对比

  • 排序性能：

    • Collections.sort()的时间复杂度为O(n log n)。
    • 对于大数据量，推荐使用并行排序（list.parallelStream().sorted()）。

  • 搜索性能：

    • 线性搜索的时间复杂度为O(n)。
    • 二分搜索的时间复杂度为O(log n)，但要求集合必须是有序的。

4.5.4 实际应用场景

  1. 排序场景

    • 对用户列表按姓名或年龄排序。
    • 对商品列表按价格或销量排序。

  2. 搜索场景

    • 在数据库中查询符合条件的记录。
    • 实现自动补全功能时快速匹配关键字。

4.5.5 注意事项

  1. 使用Comparable或Comparator时，需确保排序规则的一致性，否则可能引发IllegalArgumentException。
  2. 二分搜索前必须确保集合是有序的，否则结果不可预测。
  3. 对于自定义对象，重写equals()和hashCode()方法可以提高搜索效率。

通过本节的学习，读者可以掌握Java集合的排序与搜索技巧，并能够根据实际需求选择合适的方法优化程序性能。

Last Updated::