Sorting in Java – 在Java中进行排序

最后修改: 2016年 11月 30日


1. Overview


This article will illustrate how to apply sorting to Array, List, Set and Map in Java 7 and Java 8.

本文将说明如何在Java 7和Java 8中对ArrayListSetMap应用排序。

2. Sorting With Array


Let’s start by sorting integer arrays first using Arrays.sort() method.


We’ll define the following int arrays in a @Before jUnit method:

我们将在@Before jUnit方法中定义以下int数组。

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. Sorting Complete Array


Let’s now use the simple Array.sort() API:

现在让我们使用简单的Array.sort() API。

public void givenIntArray_whenUsingSort_thenSortedArray() {

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

The unsorted array is now fully sorted:


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

As mentioned in the official JavaDoc, Arrays.sort uses dual-pivot Quicksort on primitives. It offers O(n log(n)) performance and is typically faster than traditional (one-pivot) Quicksort implementations. However, it uses a stable, adaptive, iterative implementation of mergesort algorithm for Array of Objects.

正如官方JavaDoc中提到的那样Arrays.sortprimitives使用双枢轴Quicksort。它提供了 O(n log(n))的性能,并且通常比传统(单枢轴)Quicksort 实现更快。然而,它使用了对象Array的mergesort算法的稳定、自适应、迭代式实现。

2.2. Sorting Part of an Array


Arrays.sort has one more sort APIs – which we’ll discuss here:

Arrays.sort还有一个sort API – 我们将在这里讨论。

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

This will only sort a portion of the array, between the two indices.


Let’s have a look at a quick example:


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

The sorting will be done only on following sub-array elements (toIndex would be exclusive):


[255, 7, 88, 200]

The resultant sorted sub-array inclusive with the main array would be:


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

2.3. Java 8 Arrays.sort vs Arrays.parallelSort

2.3.Java 8 Arrays.sort vs Arrays.parallelSort

Java 8 comes with a new API – parallelSort – with a similar signature to the Arrays.sort() API:

Java 8提供了一个新的API–parallelSort,其签名与Arrays.sort() API相似。

public void givenIntArray_whenUsingParallelSort_thenArraySorted() {
    assertTrue(Arrays.equals(toSort, sortedInts));

Behind the scenes of parallelSort(), it breaks the array into different sub-arrays (as per granularity in the algorithm of parallelSort). Each sub-array is sorted with Arrays.sort() in different threads so that sort can be executed in a parallel fashion and are merged finally as a sorted array.


Note that the ForJoin common pool is used for executing these parallel tasks and then merging the results.


The result of the Arrays.parallelSort is going to be the same as Array.sort of course, it’s just a matter of leveraging multi-threading.


Finally, there are similar variants of API Arrays.sort in Arrays.parallelSort as well:

最后,在Arrays.parallelSort中也有类似的API Arrays.sort的变体。

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

3. Sorting a List


Let’s now use the Collections.sort() API in java.utils.Collections – to sort a List of Integers:


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


The List before sorting will contain the following elements:


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

And naturally, after sorting:


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

As mentioned in Oracle JavaDoc for Collections.Sort, it uses a modified mergesort and offers guaranteed n log(n) performance.

正如Oracle JavaDoc中提到的Collections.Sort,它使用一个修改过的mergesort,并提供有保证的n log(n)性能。

4. Sorting a Set


Next, let’s use Collections.sort() to sort a LinkedHashSet.


We’re using the LinkedHashSet because it maintains insertion order.


Notice how, in order to use the sort API in Collectionswe’re first wrapping the set in a list:

请注意,为了在Collections中使用sort API – 我们首先将集合包装成一个列表

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);
    integersSet = new LinkedHashSet<>(list);
      integersSet.toArray(), descSortedIntegersSet.toArray()));

The Comparator.reverseOrder() method reverses the ordering imposed by the natural ordering.


5. Sorting Map


In this section, we’ll start looking at sorting a Map – both by keys and by values.


Let’s first define the map we’ll be sorting:


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. Sorting Map by Keys


We’ll now extract keys and values entries from the HashMap and sort it based on the values of the keys in this example:


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>>() {
        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));

Note how we used the LinkedHashMap while copying the sorted Entries based on keys (because HashSet doesn’t guarantee the order of keys).


The Map before sorting :


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

The Map after sorting by keys:

Map进行排序后的by keys

[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. Sorting Map by Values


Here we will be comparing values of HashMap entries for sorting based on values of HashMap:


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>>() {
        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));

The Map before sorting:


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

The Map after sorting by values:


[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. Sorting Custom Objects


Let’s now work with a custom object:


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

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

    // standard getters, setters and toString

We’ll be using the following Employee Array for sorting example in the following sections:


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)};

We can sort arrays or collections of custom objects either:


  1. in the natural order (Using the Comparable Interface) or
  2. in the order provided by a Comparator Interface

6.1. Using Comparable

6.1.Using 可比的

The natural order in java means an order in which primitive or Object should be orderly sorted in a given array or collection.


Both java.util.Arrays and java.util.Collections have a sort() method, and It’s highly recommended that natural orders should be consistent with the semantics of equals.

java.util.Arraysjava.util.Collections 都有一个sort()方法,并且强烈建议自然顺序应该与equals的语义一致。

In this example, we will consider employees with the same name as equal:


public void givenEmpArray_SortEmpArray_thenSortedArrayinNaturalOrder() {

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

You can define the natural order for elements by implementing a Comparable interface which has compareTo() method for comparing current object and object passed as an argument.


To understand this clearly, let’s see an example Employee class which implements Comparable Interface:


public class Employee implements Comparable {

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

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

Generally, the logic for comparison will be written the method compareTo. Here we are comparing the employee order or name of the employee field. Two employees will be equal if they have the same name.


Now when Arrays.sort(employees); is called in the above code, we now know what is the logic and order which goes in sorting the employees as per the age :


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

We can see the array is sorted by name of the employee – which now becomes a natural order for Employee Class.


6.2. Using Comparator


Now, let’s sort the elements using a Comparator interface implementation – where we pass the anonymous inner class on-the-fly to the Arrays.sort() API:

现在,让我们使用Comparator接口实现对元素进行排序–在这里,我们将匿名的内部类即时传递给Arrays.sort() API。

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

Now lets sort employees based on salary – and pass in another comparator implementation:

现在让我们根据salary 对员工进行排序,并传入另一个比较器实现。

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

The sorted Employees arrays based on salary will be:


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

Note that we can use Collections.sort() in a similar fashion to sort List and Set of Objects in Natural or Custom order as described above for Arrays.


7. Sorting With Lambdas


Start with Java 8, we can use Lambdas to implement the Comparator Functional Interface.

从Java 8开始,我们可以使用Lambdas来实现Comparator功能接口。

You can have a look at the Lambdas in Java 8 writeup to brush up on the syntax.

您可以看看Java 8中的Lambdas写法,以了解语法。

Let’s replace the old comparator:


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

With the equivalent implementation, using Lambda expression:


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

Finally, let’s write the test:


public void givenArray_whenUsingSortWithLambdas_thenSortedArray() {
    Integer [] integersToSort = ArrayUtils.toObject(toSort);
    Arrays.sort(integersToSort, (a, b) -> {
        return, b);

As you can see, a much cleaner and more concise logic here.


8. Using Comparator.comparing and Comparator.thenComparing


Java 8 comes with two new APIs useful for sorting – comparing() and thenComparing() in the Comparator interface.

Java 8配备了两个对排序有用的新API – comparing() thenComparing() Comparator接口。

These are quite handy for the chaining of multiple conditions of the Comparator.


Let’s consider a scenario where we may want to compare Employee by age and then by name:


public void givenArrayObjects_whenUsingComparing_thenSortedArrayObjects() {
    List<Employee> employeesList = Arrays.asList(employees);


In this example, Employee::getAge is the sorting key for Comparator interface implementing a functional interface with compare function.


Here’s the array of Employees after sorting:


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

Here the employees are sorted based on age.


We can see John and Jessica are of same age – which means that the order logic should now take their names into account- which we can achieve with thenComparing():



After sorting with above code snippet, the elements in employee array would be sorted as:



Thus comparing() and thenComparing() definitely make more complex sorting scenarios a lot cleaner to implement.

因此, comparing()thenComparing()肯定会使更复杂的排序场景的实现变得更干净。

9. Conclusion


In this article, we saw how we can apply sorting to Array, List, Set, and Map.


We also saw a brief introduction about how features of Java 8 could be useful in sorting like usage of Lambdas, comparing() and thenComparing() and parallelSort().

我们还看到了关于Java 8的功能如何在排序中发挥作用的简要介绍,如Lambdas的使用、comparing()thenComparing()以及parallelSort()

All examples used in the article are available over on GitHub.