MK
摩柯社区 - 一个极简的技术知识社区
AI 面试

Java Collections 的排序算法实现

2022-01-176.2k 阅读

Java Collections 概述

在Java编程中，java.util.Collections 类是一个工具类，提供了大量用于操作集合（如 List、Set、Map 等）的静态方法。其中，排序是其重要功能之一。它使得开发人员可以方便地对集合中的元素进行排序，而无需手动编写复杂的排序算法。Collections 类涵盖了多种排序场景，支持对实现了 Comparable 接口的元素类型集合进行自然排序，也支持通过 Comparator 接口实现自定义排序。

自然排序（基于 Comparable 接口）

自然排序是指当集合中的元素类型实现了 java.lang.Comparable 接口时，Collections 类可按照该接口定义的比较规则对元素进行排序。Comparable 接口只有一个方法 compareTo(T o)，该方法返回一个整数值，表示当前对象与参数对象的比较结果。如果返回值小于 0，表示当前对象小于参数对象；返回值等于 0，表示两者相等；返回值大于 0，表示当前对象大于参数对象。

示例代码 - 自然排序

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

class Person implements Comparable<Person> {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }

    @Override
    public int compareTo(Person other) {
        // 按照年龄进行自然排序
        return this.age - other.age;
    }

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

public class NaturalSortingExample {
    public static void main(String[] args) {
        List<Person> personList = new ArrayList<>();
        personList.add(new Person("Alice", 25));
        personList.add(new Person("Bob", 20));
        personList.add(new Person("Charlie", 30));

        Collections.sort(personList);

        for (Person person : personList) {
            System.out.println(person);
        }
    }
}

在上述代码中，Person 类实现了 Comparable 接口，并在 compareTo 方法中定义了按照年龄进行排序的逻辑。Collections.sort 方法会根据 Person 类定义的自然排序规则对 personList 进行排序。运行结果将按照年龄从小到大输出 Person 对象。

自定义排序（基于 Comparator 接口）

当集合中的元素类型没有实现 Comparable 接口，或者需要使用不同于自然排序的规则进行排序时，可以使用 java.util.Comparator 接口。Comparator 接口包含两个主要方法：compare(T o1, T o2) 和 equals(Object obj)。其中，compare 方法用于定义两个对象的比较逻辑，返回值含义与 Comparable 接口的 compareTo 方法相同；equals 方法通常不需要重写，因为 Collections 类在排序时并不依赖此方法。

示例代码 - 自定义排序

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

class Book {
    private String title;
    private int pageCount;

    public Book(String title, int pageCount) {
        this.title = title;
        this.pageCount = pageCount;
    }

    public String getTitle() {
        return title;
    }

    public int getPageCount() {
        return pageCount;
    }

    @Override
    public String toString() {
        return "Book{" +
                "title='" + title + '\'' +
                ", pageCount=" + pageCount +
                '}';
    }
}

class BookPageCountComparator implements Comparator<Book> {
    @Override
    public int compare(Book book1, Book book2) {
        return book1.getPageCount() - book2.getPageCount();
    }
}

class BookTitleComparator implements Comparator<Book> {
    @Override
    public int compare(Book book1, Book book2) {
        return book1.getTitle().compareTo(book2.getTitle());
    }
}

public class CustomSortingExample {
    public static void main(String[] args) {
        List<Book> bookList = new ArrayList<>();
        bookList.add(new Book("Effective Java", 379));
        bookList.add(new Book("Clean Code", 464));
        bookList.add(new Book("Java Concurrency in Practice", 354));

        // 使用按页数排序的比较器
        Collections.sort(bookList, new BookPageCountComparator());
        System.out.println("按页数排序:");
        for (Book book : bookList) {
            System.out.println(book);
        }

        // 使用按标题排序的比较器
        Collections.sort(bookList, new BookTitleComparator());
        System.out.println("\n按标题排序:");
        for (Book book : bookList) {
            System.out.println(book);
        }
    }
}

在这段代码中，Book 类没有实现 Comparable 接口。我们创建了两个实现 Comparator 接口的类：BookPageCountComparator 和 BookTitleComparator，分别用于按页数和标题对 Book 对象进行排序。Collections.sort 方法接受一个 Comparator 实例作为参数，从而实现自定义排序。

Collections.sort 方法的实现原理

Collections.sort 方法在不同的JDK版本中实现略有不同，但总体上都是基于高效的排序算法。在JDK 7及之后的版本中，Collections.sort 方法对于 List 的排序主要基于 TimSort 算法。

TimSort 算法简介

TimSort 是一种稳定的、自适应的混合排序算法，结合了归并排序（Merge Sort）和插入排序（Insertion Sort）的优点。它的设计目标是在实际应用中能够高效地对各种类型的数据进行排序，尤其是在部分有序的数据上表现出色。

TimSort 的基本步骤

  1. 划分 runs：TimSort 首先将待排序的列表划分为多个子列表，称为 “runs”。每个 run 是一个已经部分有序（升序或降序）的子序列。它通过扫描列表，识别出这些自然有序的子序列。如果找不到自然有序的子序列，就使用插入排序创建一个最小长度的 run。
  2. 合并 runs：划分完 runs 后，TimSort 使用归并排序的思想将这些 runs 逐步合并成一个有序的列表。在合并过程中，为了保证稳定性，TimSort 会仔细处理相等元素的顺序，确保相等元素在排序前后的相对顺序不变。

示例代码分析 - TimSort 的体现

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

public class TimSortExample {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>();
        numbers.add(5);
        numbers.add(3);
        numbers.add(8);
        numbers.add(1);
        numbers.add(9);

        Collections.sort(numbers);

        System.out.println("排序后的列表: " + numbers);
    }
}

在上述代码中，Collections.sort 方法会对 numbers 列表执行 TimSort 算法。首先，它会划分 runs，例如，可能会识别出 [3, 5] 作为一个升序 run，[1] 作为一个单独的 run，[8, 9] 作为另一个升序 run。然后，通过归并排序的方式将这些 runs 合并，最终得到一个完全有序的列表 [1, 3, 5, 8, 9]。

与其他排序算法的比较

与传统的排序算法如冒泡排序（Bubble Sort）、选择排序（Selection Sort）相比，TimSort 具有更高的效率。冒泡排序和选择排序的时间复杂度为 (O(n^2))，而 TimSort 的平均时间复杂度为 (O(n log n))，在处理大规模数据时性能优势明显。

冒泡排序示例代码

import java.util.Arrays;

public class BubbleSortExample {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] numbers = {5, 3, 8, 1, 9};
        bubbleSort(numbers);
        System.out.println("冒泡排序后的数组: " + Arrays.toString(numbers));
    }
}

选择排序示例代码

import java.util.Arrays;

public class SelectionSortExample {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] numbers = {5, 3, 8, 1, 9};
        selectionSort(numbers);
        System.out.println("选择排序后的数组: " + Arrays.toString(numbers));
    }
}

通过对比可以看出，冒泡排序和选择排序在每一轮比较中都需要进行多次元素交换操作，而 TimSort 通过巧妙的 run 划分和合并策略，减少了不必要的比较和交换，从而提高了排序效率。

对不可变集合的排序

在Java 9及之后的版本中，java.util.Collections 类提供了创建不可变集合的方法，如 Collections.unmodifiableList、Collections.unmodifiableSet 等。对于不可变集合，不能直接调用 sort 方法进行排序，因为这会违反不可变的原则。

处理方式

要对不可变集合进行排序，一种常见的做法是先将不可变集合转换为可变集合（如 ArrayList 或 HashSet），对可变集合进行排序，然后再将排序后的可变集合转换回不可变集合。

示例代码 - 对不可变 List 排序

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

public class SortImmutableListExample {
    public static void main(String[] args) {
        // 创建一个不可变 List
        List<Integer> immutableList = Collections.unmodifiableList(
                List.of(5, 3, 8, 1, 9)
        );

        // 将不可变 List 转换为可变 List
        List<Integer> mutableList = new ArrayList<>(immutableList);

        // 对可变 List 进行排序
        Collections.sort(mutableList);

        // 将排序后的可变 List 转换回不可变 List
        List<Integer> sortedImmutableList = Collections.unmodifiableList(mutableList);

        System.out.println("排序后的不可变 List: " + sortedImmutableList);
    }
}

在上述代码中，首先创建了一个不可变的 List。然后，通过构造函数将其转换为 ArrayList 进行排序。最后，将排序后的 ArrayList 再次转换为不可变的 List。

注意事项

在进行这种转换操作时，需要注意性能问题。尤其是对于大规模集合，多次转换可能会消耗较多的时间和内存。此外，在转换过程中要确保数据的一致性，避免在转换过程中数据被意外修改。

对 Map 集合的排序

java.util.Map 本身并没有直接的排序方法，因为 Map 主要用于存储键值对，其元素的顺序通常是无序的。然而，我们可以根据键或值对 Map 进行排序，并将排序结果存储在其他有序集合中。

根据键排序

要根据键对 Map 进行排序，可以将 Map 的键提取到一个 List 中，对该 List 进行排序，然后遍历排序后的 List 来获取对应的键值对。

示例代码 - 根据键排序 Map

import java.util.*;

public class SortMapByKeyExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("banana", 3);
        map.put("apple", 2);
        map.put("cherry", 1);

        List<String> keys = new ArrayList<>(map.keySet());
        Collections.sort(keys);

        Map<String, Integer> sortedMap = new LinkedHashMap<>();
        for (String key : keys) {
            sortedMap.put(key, map.get(key));
        }

        System.out.println("根据键排序后的 Map: " + sortedMap);
    }
}

在这段代码中，首先将 Map 的键提取到 List 中，对 List 进行排序。然后，通过遍历排序后的 List，将键值对按顺序放入 LinkedHashMap 中，以保持插入顺序，从而实现根据键排序的 Map。

根据值排序

根据值对 Map 进行排序稍微复杂一些，需要将 Map 转换为一个包含键值对的 List，并使用自定义的 Comparator 对该 List 进行排序。

示例代码 - 根据值排序 Map

import java.util.*;

public class SortMapByValueExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("banana", 3);
        map.put("apple", 2);
        map.put("cherry", 1);

        List<Map.Entry<String, Integer>> list = new ArrayList<>(map.entrySet());
        Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                return o1.getValue().compareTo(o2.getValue());
            }
        });

        Map<String, Integer> sortedMap = new LinkedHashMap<>();
        for (Map.Entry<String, Integer> entry : list) {
            sortedMap.put(entry.getKey(), entry.getValue());
        }

        System.out.println("根据值排序后的 Map: " + sortedMap);
    }
}

在上述代码中，首先将 Map 的 entrySet 转换为 List。然后，使用自定义的 Comparator 根据值对 List 进行排序。最后，将排序后的 List 中的键值对放入 LinkedHashMap 中，以保持顺序。

并发环境下的排序

在并发编程中，对集合进行排序需要特别小心，因为多个线程同时访问和修改集合可能会导致数据不一致或其他并发问题。

使用并发安全的集合

Java提供了一些并发安全的集合类，如 ConcurrentHashMap、CopyOnWriteArrayList 等。然而，这些集合类本身并没有直接提供排序方法。如果需要在并发环境下对这些集合进行排序，一种方法是将数据复制到一个普通的可变集合中，在单线程环境下进行排序，然后再将结果复制回并发安全的集合（如果需要的话）。

示例代码 - 对 CopyOnWriteArrayList 排序

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

public class SortConcurrentArrayListExample {
    public static void main(String[] args) {
        CopyOnWriteArrayList<Integer> concurrentList = new CopyOnWriteArrayList<>();
        concurrentList.add(5);
        concurrentList.add(3);
        concurrentList.add(8);
        concurrentList.add(1);
        concurrentList.add(9);

        List<Integer> tempList = new ArrayList<>(concurrentList);
        Collections.sort(tempList);

        CopyOnWriteArrayList<Integer> sortedConcurrentList = new CopyOnWriteArrayList<>(tempList);

        System.out.println("排序后的并发安全 List: " + sortedConcurrentList);
    }
}

在这段代码中，首先创建了一个 CopyOnWriteArrayList。然后，将其内容复制到一个普通的 ArrayList 中进行排序。最后，将排序后的 ArrayList 内容复制到一个新的 CopyOnWriteArrayList 中。

使用并行流进行排序

从Java 8开始，Stream API 提供了并行流（Parallel Stream）的功能，可以在多核处理器上并行处理数据。对于 List 类型的集合，可以使用并行流进行排序。

示例代码 - 使用并行流排序

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class ParallelStreamSortExample {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>();
        numbers.add(5);
        numbers.add(3);
        numbers.add(8);
        numbers.add(1);
        numbers.add(9);

        List<Integer> sortedNumbers = numbers.parallelStream()
               .sorted()
               .collect(Collectors.toList());

        System.out.println("使用并行流排序后的列表: " + sortedNumbers);
    }
}

在上述代码中，通过调用 parallelStream 方法将 List 转换为并行流，然后调用 sorted 方法进行排序，并最终将结果收集到一个新的 List 中。使用并行流可以充分利用多核处理器的优势，提高排序效率，尤其是在处理大规模数据时。但需要注意的是，并行流的使用也可能带来一些开销，如线程创建和管理的开销，因此在选择是否使用并行流时需要根据具体的应用场景和数据规模进行权衡。

性能优化与调优

在对 Java Collections 进行排序时，性能优化是一个重要的考虑因素。以下是一些性能优化和调优的建议。

选择合适的集合类型

不同的集合类型在排序性能上可能会有显著差异。例如，ArrayList 基于数组实现，在随机访问和排序操作上通常比 LinkedList 更高效，因为 LinkedList 需要遍历链表来访问元素。因此，在已知需要对集合进行排序的情况下，优先选择 ArrayList 作为存储结构。

示例对比 - ArrayList 和 LinkedList 的排序性能

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

public class ListTypeSortPerformanceExample {
    public static void main(String[] args) {
        List<Integer> arrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();

        for (int i = 0; i < 100000; i++) {
            arrayList.add((int) (Math.random() * 100000));
            linkedList.add((int) (Math.random() * 100000));
        }

        long startTime = System.currentTimeMillis();
        Collections.sort(arrayList);
        long endTime = System.currentTimeMillis();
        System.out.println("ArrayList 排序时间: " + (endTime - startTime) + " 毫秒");

        startTime = System.currentTimeMillis();
        Collections.sort(linkedList);
        endTime = System.currentTimeMillis();
        System.out.println("LinkedList 排序时间: " + (endTime - startTime) + " 毫秒");
    }
}

通过上述代码的实际运行可以发现，对于大规模数据的排序，ArrayList 的性能明显优于 LinkedList。

减少不必要的操作

在排序前，尽量减少对集合的不必要操作，如频繁的插入和删除。因为每次插入或删除操作可能会导致集合内部结构的调整，从而增加排序的开销。如果可能，在集合数据稳定后再进行排序。

预排序处理

对于部分有序的数据，可以利用 TimSort 等排序算法的自适应特性。在进行 Collections.sort 之前，如果能够对数据进行一些简单的预排序处理，使数据更加有序，那么排序算法的效率会更高。例如，如果知道数据的大致范围，可以先进行一些局部的排序或分组操作，让 TimSort 在划分 runs 时能够更高效地识别出有序子序列。

使用合适的比较器

在自定义排序时，确保比较器的实现尽可能高效。避免在比较器中进行复杂的计算或数据库查询等耗时操作。如果可能，尽量复用已有的比较逻辑，例如使用 String 类的 compareTo 方法来对字符串进行比较，而不是自己重新实现复杂的字符串比较逻辑。

总结

在Java编程中，Collections 类的排序功能为开发人员提供了便捷的集合排序方式。通过自然排序（基于 Comparable 接口）和自定义排序（基于 Comparator 接口），可以满足各种不同的排序需求。TimSort 算法作为 Collections.sort 的核心实现，结合了多种排序算法的优点，在实际应用中表现出色。同时，在处理不可变集合、Map 集合以及并发环境下的排序时，需要采用相应的策略和方法。通过合理选择集合类型、减少不必要操作、进行预排序处理以及使用高效的比较器等性能优化手段，可以进一步提升排序的效率和应用程序的整体性能。掌握这些关于 Java Collections 排序算法实现的知识和技巧，对于编写高效、健壮的Java程序至关重要。