Java排序指南

最后修改:2024年1月5日

by baeldung

1. 概述

本文将详细介绍如何在Java 7和Java 8中对数组(Array)、列表(List)、集合(Set)和映射(Map)进行排序操作。

2. 数组排序

首先使用Arrays.sort()方法对整数数组进行排序。我们在jUnit的@Before方法中定义以下数组：

@Before
public void initVariables () {
    toSort = new int[] 
      { 5, 1, 89, 255, 7, 88, 200, 123, 66 }; 
    sortedInts = new int[] 
      {1, 5, 7, 66, 88, 89, 123, 200, 255};
    sortedRangeInts = new int[] 
      {5, 1, 89, 7, 88, 200, 255, 123, 66};
    ...
}

2.1 排序整个数组

使用简单的Array.sort() API：

@Test
public void givenIntArray_whenUsingSort_thenSortedArray() {
    Arrays.sort(toSort);

    assertTrue(Arrays.equals(toSort, sortedInts));
}

未排序数组现在完全排序：

[1, 5, 7, 66, 88, 89, 123, 200, 255]

⚠️ 根据官方JavaDoc，Arrays.sort对基本类型使用双轴快速排序。它提供O(n log(n))性能，通常比传统（单轴）快速排序实现更快。但对于对象数组，则使用稳定、自适应、迭代的归并排序实现。

2.2 排序数组的一部分

Arrays.sort还有一个重载API：

Arrays.sort(int[] a, int fromIndex, int toIndex)

这仅对两个索引之间的部分数组进行排序。看个简单例子：

@Test
public void givenIntArray_whenUsingRangeSort_thenRangeSortedArray() {
    Arrays.sort(toSort, 3, 7);
 
    assertTrue(Arrays.equals(toSort, sortedRangeInts));
}

排序仅作用于以下子数组元素（toIndex是排他的）：

[255, 7, 88, 200]

最终包含主数组的排序结果：

[5, 1, 89, 7, 88, 200, 255, 123, 66]

2.3 Java 8中的Arrays.sort与Arrays.parallelSort

Java 8引入了新API——parallelSort，签名与Arrays.sort()类似：

@Test 
public void givenIntArray_whenUsingParallelSort_thenArraySorted() {
    Arrays.parallelSort(toSort);
 
    assertTrue(Arrays.equals(toSort, sortedInts));
}

✅ parallelSort()内部将数组拆分为不同子数组（根据parallelSort算法的粒度）。每个子数组在不同线程中使用Arrays.sort()排序，使排序可以并行执行，最后合并为排序后的数组。

⚠️ 注意：使用ForJoin公共池执行这些并行任务并合并结果。

Arrays.parallelSort的结果当然与Array.sort相同，只是利用了多线程。

最后，Arrays.parallelSort也有类似变体：

Arrays.parallelSort (int [] a, int fromIndex, int toIndex);

3. List排序

现在使用java.utils.Collections中的Collections.sort() API对整数列表进行排序：

@Test
public void givenList_whenUsingSort_thenSortedList() {
    List<Integer> toSortList = Ints.asList(toSort);
    Collections.sort(toSortList);

    assertTrue(Arrays.equals(toSortList.toArray(), 
    ArrayUtils.toObject(sortedInts)));
}

排序前的List包含以下元素：

[5, 1, 89, 255, 7, 88, 200, 123, 66]

排序后自然为：

[1, 5, 7, 66, 88, 89, 123, 200, 255]

⚠️ 根据Oracle JavaDoc，Collections.Sort使用改进的归并排序，保证n log(n)性能。

4. Set排序

接下来使用Collections.sort()对LinkedHashSet排序。我们选择LinkedHashSet因为它保持插入顺序。

注意：为了使用Collections中的sort API——我们先将Set包装成List：

@Test
public void givenSet_whenUsingSort_thenSortedSet() {
    Set<Integer> integersSet = new LinkedHashSet<>(Ints.asList(toSort));
    Set<Integer> descSortedIntegersSet = new LinkedHashSet<>(
      Arrays.asList(new Integer[] 
        {255, 200, 123, 89, 88, 66, 7, 5, 1}));
        
    List<Integer> list = new ArrayList<Integer>(integersSet);
    Collections.sort(list, Comparator.reverseOrder());
    integersSet = new LinkedHashSet<>(list);
        
    assertTrue(Arrays.equals(
      integersSet.toArray(), descSortedIntegersSet.toArray()));
}

Comparator.reverseOrder()方法反转自然顺序的排序规则。

5. Map排序

本节将介绍Map排序——按键和按值两种方式。

首先定义要排序的Map：

@Before
public void initVariables () {
    ....
    HashMap<Integer, String> map = new HashMap<>();
    map.put(55, "John");
    map.put(22, "Apple");
    map.put(66, "Earl");
    map.put(77, "Pearl");
    map.put(12, "George");
    map.put(6, "Rocky");
    ....
}

5.1 按键排序Map

我们从HashMap中提取键值对，并根据键的值排序：

@Test
public void givenMap_whenSortingByKeys_thenSortedMap() {
    Integer[] sortedKeys = new Integer[] { 6, 12, 22, 55, 66, 77 };

    List<Map.Entry<Integer, String>> entries 
      = new ArrayList<>(map.entrySet());
    Collections.sort(entries, new Comparator<Entry<Integer, String>>() {
        @Override
        public int compare(
          Entry<Integer, String> o1, Entry<Integer, String> o2) {
            return o1.getKey().compareTo(o2.getKey());
        }
    });
    Map<Integer, String> sortedMap = new LinkedHashMap<>();
    for (Map.Entry<Integer, String> entry : entries) {
        sortedMap.put(entry.getKey(), entry.getValue());
    }
        
    assertTrue(Arrays.equals(sortedMap.keySet().toArray(), sortedKeys));
}

✅ 注意：我们使用LinkedHashMap复制基于键排序的条目（因为HashSet不保证键的顺序）。

排序前的Map：

[Key: 66 , Value: Earl] 
[Key: 22 , Value: Apple] 
[Key: 6 , Value: Rocky] 
[Key: 55 , Value: John] 
[Key: 12 , Value: George] 
[Key: 77 , Value: Pearl]

按键排序后的Map：

[Key: 6 , Value: Rocky] 
[Key: 12 , Value: George] 
[Key: 22 , Value: Apple] 
[Key: 55 , Value: John] 
[Key: 66 , Value: Earl] 
[Key: 77 , Value: Pearl]

5.2 按值排序Map

这里我们将比较HashMap条目的值，实现基于值的排序：

@Test
public void givenMap_whenSortingByValues_thenSortedMap() {
    String[] sortedValues = new String[] 
      { "Apple", "Earl", "George", "John", "Pearl", "Rocky" };

    List<Map.Entry<Integer, String>> entries 
      = new ArrayList<>(map.entrySet());
    Collections.sort(entries, new Comparator<Entry<Integer, String>>() {
        @Override
        public int compare(
          Entry<Integer, String> o1, Entry<Integer, String> o2) {
            return o1.getValue().compareTo(o2.getValue());
        }
    });
    Map<Integer, String> sortedMap = new LinkedHashMap<>();
    for (Map.Entry<Integer, String> entry : entries) {
        sortedMap.put(entry.getKey(), entry.getValue());
    }
        
    assertTrue(Arrays.equals(sortedMap.values().toArray(), sortedValues));
}

排序前的Map：

[Key: 66 , Value: Earl] 
[Key: 22 , Value: Apple] 
[Key: 6 , Value: Rocky] 
[Key: 55 , Value: John] 
[Key: 12 , Value: George] 
[Key: 77 , Value: Pearl]

按值排序后的Map：

[Key: 22 , Value: Apple] 
[Key: 66 , Value: Earl] 
[Key: 12 , Value: George] 
[Key: 55 , Value: John] 
[Key: 77 , Value: Pearl] 
[Key: 6 , Value: Rocky]

6. 自定义对象排序

现在处理自定义对象：

public class Employee implements Comparable {
    private String name;
    private int age;
    private double salary;

    public Employee(String name, int age, double salary) {
        ...
    }

    // 标准getter、setter和toString
}

后续排序示例将使用以下Employee数组：

@Before
public void initVariables () {
    ....    
    employees = new Employee[] { 
      new Employee("John", 23, 5000), new Employee("Steve", 26, 6000), 
      new Employee("Frank", 33, 7000), new Employee("Earl", 43, 10000), 
      new Employee("Jessica", 23, 4000), new Employee("Pearl", 33, 6000)};
    
    employeesSorted = new Employee[] {
      new Employee("Earl", 43, 10000), new Employee("Frank", 33, 70000),
      new Employee("Jessica", 23, 4000), new Employee("John", 23, 5000), 
      new Employee("Pearl", 33, 4000), new Employee("Steve", 26, 6000)};
    
    employeesSortedByAge = new Employee[] { 
      new Employee("John", 23, 5000), new Employee("Jessica", 23, 4000), 
      new Employee("Steve", 26, 6000), new Employee("Frank", 33, 70000), 
      new Employee("Pearl", 33, 4000), new Employee("Earl", 43, 10000)};
}

自定义对象数组或集合的排序方式有两种：

  1. 自然顺序（使用Comparable接口）
  2. Comparator接口提供的顺序

6.1 使用Comparable

Java中的自然顺序指基本类型或对象在给定数组或集合中应该有序排列的顺序。

java.util.Arrays和java.util.Collections都有sort()方法，强烈建议自然顺序应与equals的语义一致。

本例中，我们将同名员工视为相等：

@Test
public void givenEmpArray_SortEmpArray_thenSortedArrayinNaturalOrder() {
    Arrays.sort(employees);

    assertTrue(Arrays.equals(employees, employeesSorted));
}

通过实现Comparable接口定义元素的自然顺序，该接口包含compareTo()方法用于比较当前对象和参数对象。

看实现Comparable接口的Employee类示例：

public class Employee implements Comparable {
    ...

    @Override
    public boolean equals(Object obj) {
        return ((Employee) obj).getName().equals(getName());
    }

    @Override
    public int compareTo(Object o) {
        Employee e = (Employee) o;
        return getName().compareTo(e.getName());
    }
}

比较逻辑通常写在compareTo方法中。这里我们比较员工的name字段。同名员工视为相等。

当调用Arrays.sort(employees);时，排序逻辑按员工名称进行：

[("Earl", 43, 10000),("Frank", 33, 70000), ("Jessica", 23, 4000),
 ("John", 23, 5000),("Pearl", 33, 4000), ("Steve", 26, 6000)]

可见数组按员工名称排序——这成为Employee类的自然顺序。

6.2 使用Comparator

现在使用Comparator接口实现排序——我们将匿名内部类直接传递给Arrays.sort() API：

@Test
public void givenIntegerArray_whenUsingSort_thenSortedArray() {
    Integer [] integers = ArrayUtils.toObject(toSort);
    Arrays.sort(integers, new Comparator<Integer>() {
        @Override
        public int compare(Integer a, Integer b) {
            return Integer.compare(a, b);
        }
    });
 
    assertTrue(Arrays.equals(integers, ArrayUtils.toObject(sortedInts)));
}

现在按salary排序员工——传入另一个Comparator实现：

Arrays.sort(employees, new Comparator<Employee>() {
    @Override
    public int compare(Employee o1, Employee o2) {
       return Double.compare(o1.getSalary(), o2.getSalary());
    }
 });

按salary排序后的员工数组：

[(Jessica,23,4000.0), (John,23,5000.0), (Pearl,33,6000.0), (Steve,26,6000.0), 
(Frank,33,7000.0), (Earl,43,10000.0)]

✅ 注意：Collections.sort()也能以类似方式对List和Set对象进行自然顺序或自定义顺序排序。

7. 使用Lambda表达式排序

从Java 8开始，可以使用Lambda表达式实现Comparator函数式接口。

可以参考Java 8中的Lambda表达式复习语法。

将旧式Comparator：

Comparator<Integer> c  = new Comparator<>() {
    @Override
    public int compare(Integer a, Integer b) {
        return Integer.compare(a, b);
    }
}

替换为等效的Lambda表达式实现：

Comparator<Integer> c = (a, b) -> Integer.compare(a, b);

最后编写测试：

@Test
public void givenArray_whenUsingSortWithLambdas_thenSortedArray() {
    Integer [] integersToSort = ArrayUtils.toObject(toSort);
    Arrays.sort(integersToSort, (a, b) -> {
        return Integer.compare(a, b);
    });
 
    assertTrue(Arrays.equals(integersToSort, 
      ArrayUtils.toObject(sortedInts)));
}

✅ 代码更简洁清晰，逻辑一目了然。

8. 使用Comparator.comparing和Comparator.thenComparing

Java 8在Comparator接口中引入了两个实用API——comparing()和thenComparing()。

这些方法对链式多个Comparator条件非常方便。

考虑需要先按age再按name比较Employee的场景：

@Test
public void givenArrayObjects_whenUsingComparing_thenSortedArrayObjects() {
    List<Employee> employeesList = Arrays.asList(employees);
    employees.sort(Comparator.comparing(Employee::getAge));

    assertTrue(Arrays.toString(employees.toArray())
      .equals(sortedArrayString));
}

这里Employee::getAge是Comparator接口的排序键，实现了带compare函数的函数式接口。

排序后的员工数组：

[(John,23,5000.0), (Jessica,23,4000.0), (Steve,26,6000.0), (Frank,33,7000.0), 
(Pearl,33,6000.0), (Earl,43,10000.0)]

员工按age排序。可见John和Jessica年龄相同——此时应考虑姓名顺序，这可通过thenComparing()实现：

... 
employees.sort(Comparator.comparing(Employee::getAge)
  .thenComparing(Employee::getName)); 
...

使用上述代码排序后，员工数组元素顺序为：

[(Jessica,23,4000.0), 
 (John,23,5000.0), 
 (Steve,26,6000.0), 
 (Frank,33,7000.0), 
 (Pearl,33,6000.0), 
 (Earl,43,10000.0)
]

✅ comparing()和thenComparing()确实让复杂排序场景的实现更简洁。

9. 总结

本文介绍了如何对Array、List、Set和Map应用排序。

我们还简要介绍了Java 8特性在排序中的应用，如Lambda表达式、comparing()、thenComparing()和parallelSort()。

本文所有示例代码可在GitHub获取。

原始标题:Sorting in Java

« 上一篇： Java Web周报，第153期
» 下一篇： Java NIO2异步通道API指南