Java 中的数组排序

学习借助Comparable和Comparator接口、Arrays.sort()和Stream.sorted() API以多种方式对 Java 基元数组、字符串和自定义对象进行排序。

我们将学习以自然顺序、逆序和任何其他自定义顺序对数组进行排序。

1. 数组排序基础知识

无论我们使用哪种 Java API 进行排序，排序功能背后的基本概念都保持不变。

所有内置API均默认支持自然顺序排序。数字类型按升序排序，字符串按字典顺序（字典顺序）排序，自定义对象按Comparable接口实现的顺序排序。
要按相反顺序排序，我们可以使用Comparator.reverseOrder()排序方法。
要按自定义顺序排序，我们必须创建该接口的实例Comparator并在其中提供相关的排序行为。然后我们将比较器的实例传递给排序 API。

现在让我们深入研究演示数组排序的 Java 程序。对于自定义排序，我们将使用User类的实例。请注意，该字段支持默认id排序。

public class User implements Comparable<User> { public long id; public String firstName; public String lastName; //Add getters and setters @Override public int compareTo(final User user) { if(user == null ) { return -1; } else { return (int)(this.id - user.id); } } }

2.Arrays.sort() 和 Arrays.parallelSort()

java.util.Arrays 类提供了许多实用的静态方法。sort() API 也是这些方法之一，它有助于对给定的数组进行排序。

sort() API 的实现是一个稳定的、自适应的迭代归并排序，当输入数组部分有序时，它需要远少于 n log(n) 次比较。当输入数组是随机排序的时，它提供了传统归并排序的性能。如果输入数组几乎有序，该实现需要大约 n 次比较。

parallelSort() API 的实现是双轴快速排序，在所有数据集上都提供 O(n log(n)) 的性能，通常比传统的单轴快速排序实现更快。

public static void sort(array, ?comparator) public static void parallelSort(array, ?comparator)

2.1. 按自然顺序排序

Java 程序用于对字符串数组按默认顺序进行排序。请注意，String 类已经实现了 Comparable 接口。

String[] tokens = {"A","C","B","E","D"}; Arrays.sort(tokens); //[A, B, C, D, E]

2.2. 按逆序排序

Java 程序使用 Comparator.reverseOrder() 来反转自然顺序。

String[] tokens = {"A","C","B","E","D"}; Arrays.sort(tokens, Collections.reverseOrder()); //[E, D, C, B, A]

2.3. 自定义排序

我们按照用户的名字对用户数组进行排序。

User[] users = getUsersArray(); Comparator firstNameSorter = Comparator.comparing(User::getFirstName); Arrays.sort(users, firstNameSorter);

要按多个字段进行排序，就像 SQL 的 group by 子句一样，我们可以创建一个复杂的 Comparator 实例并将其用于排序。

Comparator fullNameSorter = Comparator.comparing(Employee::getFirstName) .thenComparing(Employee::getLastName); Arrays.sort(employees, fullNameSorter);

3. 使用 Stream API 对数组进行排序

我们可以使用 Stream.sorted() 方法对原始数组或自定义对象数组进行排序，方式与使用 Arrays.sort() API 非常相似。

sorted() API 返回一个流，其中包含根据自然顺序排序的元素。
如果此流的元素不可比较，当执行终端操作时可能会抛出 java.lang.ClassCastException 异常。
它还接受一个可选的比较器实例，用于实现自定义排序行为。

对于有序流（例如，从有序集合生成的流，如 ArrayList），排序是稳定的。对于无序流（例如，从 HashMap 生成的流），不保证稳定性。

Stream<T> sorted() Stream<T> sorted(?comparator)

//1. 自然排序 User[] sortedUserArray = Stream.of(userArray) .sorted() .toArray(User[]::new); //2. 逆序排序 User[] sortedUserArray = Stream.of(userArray) .sorted(Comparator.reverseOrder()) .toArray(User[]::new); //3. 自定义排序 Comparator nameComparator = Comparator.comparing(Employee::getName) .thenComparing(Employee::getId) User[] sortedUserArray = Stream.of(userArray) .sorted(nameComparator) .toArray(User[]::new);