Java 中的数组排序

文
章
目
录

• 1. 数组排序基础知识
• 2.Arrays.sort() 和 Arrays.parallelSort()
• 2.1. 按自然顺序排序
• 2.2. 按逆序排序
• 2.3. 自定义排序
• 3. 使用 Stream API 对数组进行排序
• 4. 结论

学习借助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);

4. 结论

在这个示例中，我们学会了使用 Arrays.sort() 和 Stream API 对数组进行排序。我们学会了按自然顺序、逆序以及自定义顺序进行排序。