1. Overview
1.概述
This article will illustrate how to apply sorting to Array, List, Set and Map in Java 7 and Java 8.
本文将说明如何在Java 7和Java 8中对Array、List、Set和Map应用排序。
2. Sorting With Array
2.用Array进行排序
Let’s start by sorting integer arrays first using Arrays.sort() method.
让我们先用Arrays.sort()方法对整数阵列进行排序。
We’ll define the following int arrays in a @Before jUnit method:
我们将在@Before jUnit方法中定义以下int数组。
@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. Sorting Complete Array
2.1.对完整数组进行排序
Let’s now use the simple Array.sort() API:
现在让我们使用简单的Array.sort() API。
@Test
public void givenIntArray_whenUsingSort_thenSortedArray() {
Arrays.sort(toSort);
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.sort对primitives使用双枢轴Quicksort。它提供了 O(n log(n))的性能，并且通常比传统（单枢轴）Quicksort 实现更快。然而，它使用了对象Array的mergesort算法的稳定、自适应、迭代式实现。
2.2. Sorting Part of an Array
2.2.对数组的一部分进行排序
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:
让我们看一下一个快速的例子。
@Test
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):
排序将只在以下子数组元素上进行（toIndex将是排他的）。
[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相似。
@Test
public void givenIntArray_whenUsingParallelSort_thenArraySorted() {
Arrays.parallelSort(toSort);
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.
在parallelSort()的幕后，它将数组分成不同的子数组（按照parallelSort算法中的粒度）。每个子数组在不同的线程中用Arrays.sort()进行排序，这样sort就可以以并行的方式执行，最后合并为一个排序的数组。
Note that the ForJoin common pool is used for executing these parallel tasks and then merging the results.
请注意，ForJoin公共池被用来执行这些并行任务，然后合并结果。
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.
Arrays.parallelSort的结果将与Array.sort相同，当然，这只是一个利用多线程的问题。
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
3.对List进行排序
Let’s now use the Collections.sort() API in java.utils.Collections – to sort a List of Integers:
现在让我们使用Collections.sort()中的APIjava.utils.Collections-来对一个List的整数进行排序。
@Test
public void givenList_whenUsingSort_thenSortedList() {
List<Integer> toSortList = Ints.asList(toSort);
Collections.sort(toSortList);
assertTrue(Arrays.equals(toSortList.toArray(),
ArrayUtils.toObject(sortedInts)));
}The List before sorting will contain the following elements:
排序前的List将包含以下元素。
[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
4.对一个集进行排序
Next, let’s use Collections.sort() to sort a LinkedHashSet.
接下来，让我们使用Collections.sort()来对一个LinkedHashSet进行排序。
We’re using the LinkedHashSet because it maintains insertion order.
我们使用LinkedHashSet，因为它可以保持插入顺序。
Notice how, in order to use the sort API in Collections – we’re first wrapping the set in a list:
请注意，为了在Collections中使用sort API – 我们首先将集合包装成一个列表。
@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(Comparator.reverseOrder());
integersSet = new LinkedHashSet<>(list);
assertTrue(Arrays.equals(
integersSet.toArray(), descSortedIntegersSet.toArray()));
}The Comparator.reverseOrder() method reverses the ordering imposed by the natural ordering.
Comparator.reverseOrder()方法颠倒了自然排序所强加的排序。
5. Sorting Map
5.排序地图
In this section, we’ll start looking at sorting a Map – both by keys and by values.
在本节中，我们将开始研究对Map进行排序–包括按键和按值。
Let’s first define the map we’ll be sorting:
让我们首先定义一下我们要分类的地图。
@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. Sorting Map by Keys
5.1.通过键值对Map进行排序
We’ll now extract keys and values entries from the HashMap and sort it based on the values of the keys in this example:
我们现在要从HashMap中提取keys和values条目，并根据本例中的键值对其排序。
@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));
}Note how we used the LinkedHashMap while copying the sorted Entries based on keys (because HashSet doesn’t guarantee the order of keys).
注意我们是如何使用LinkedHashMap同时根据键值复制排序的Entries（因为HashSet不能保证键值的顺序）。
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
5.2.按数值对Map进行排序
Here we will be comparing values of HashMap entries for sorting based on values of HashMap:
这里我们将比较HashMap条目的值，以便根据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));
}The Map before sorting:
排序前的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]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
6.对自定义对象进行排序
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:
在下面的章节中，我们将使用下面的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)};
}We can sort arrays or collections of custom objects either:
我们也可以对数组或自定义对象的集合进行排序。
- in the natural order (Using the Comparable Interface) or
- 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.
java中的自然顺序是指在一个给定的数组或集合中，基元或对象应该被有序地排序的一个顺序。
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.Arrays和java.util.Collections 都有一个sort()方法，并且强烈建议自然顺序应该与equals的语义一致。。
In this example, we will consider employees with the same name as equal:
在这个例子中，我们将把具有相同姓名的员工视为平等。
@Test
public void givenEmpArray_SortEmpArray_thenSortedArrayinNaturalOrder() {
Arrays.sort(employees);
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.
你可以通过实现一个Comparable接口来定义元素的自然顺序，该接口有compareTo()方法来比较当前对象和作为参数传递的对象。
To understand this clearly, let’s see an example Employee class which implements Comparable Interface:
为了清楚地理解这一点，让我们看一个例子Employee类，它实现了ComparableInterface。
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());
}
}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.
一般来说，比较的逻辑将被写入方法compareTo。在这里，我们要比较雇员的顺序或雇员字段的名称。如果两个雇员有相同的名字，他们将是相等的。
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 :
现在，当Arrays.sort(employees);在上述代码中被调用时，我们现在知道了根据年龄对雇员进行排序的逻辑和顺序。
[("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.
我们可以看到数组是按照雇员的名字排序的–现在这成为Employee类的自然顺序。
6.2. Using Comparator
6.2.使用比较器
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。
@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)));
}Now lets sort employees based on salary – and pass in another comparator implementation:
现在让我们根据salary 对员工进行排序，并传入另一个比较器实现。
Arrays.sort(employees, new Comparator<Employee>() {
@Override
public int compare(Employee o1, Employee o2) {
return Double.compare(o1.getSalary(), o2.getSalary());
}
});The sorted Employees arrays based on salary will be:
基于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)]
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.
请注意，我们可以以类似的方式使用Collections.sort()来对List和Set的对象按自然或自定义顺序进行排序，就像上面对数组所描述的那样。
7. Sorting With Lambdas
7.用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<>() {
@Override
public int compare(Integer a, Integer b) {
return Integer.compare(a, b);
}
}With the equivalent implementation, using Lambda expression:
与之相当的实现，使用Lambda表达式。
Comparator<Integer> c = (a, b) -> Integer.compare(a, b);Finally, let’s write the test:
最后，我们来写测试。
@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)));
}As you can see, a much cleaner and more concise logic here.
正如你所看到的，这里的逻辑更干净、更简明。
8. Using Comparator.comparing and Comparator.thenComparing
8.使用Comparator.comparing和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.
这些对Comparator的多个条件的连锁是相当方便的。
Let’s consider a scenario where we may want to compare Employee by age and then by name:
让我们考虑一个场景，我们可能想通过年龄和名字来比较雇员。
@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));
}In this example, Employee::getAge is the sorting key for Comparator interface implementing a functional interface with compare function.
在这个例子中，Employee::getAge是Comparator接口的排序键，实现了一个具有比较功能的接口。
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():
我们可以看到John和Jessica年龄相同–这意味着现在的顺序逻辑应该考虑到他们的名字–我们可以通过thenComparing()实现。
...
employees.sort(Comparator.comparing(Employee::getAge)
.thenComparing(Employee::getName));
...
After sorting with above code snippet, the elements in employee array would be sorted as:
用上述代码片段进行排序后，雇员数组中的元素将被排序为。
[(Jessica,23,4000.0),
(John,23,5000.0),
(Steve,26,6000.0),
(Frank,33,7000.0),
(Pearl,33,6000.0),
(Earl,43,10000.0)
]Thus comparing() and thenComparing() definitely make more complex sorting scenarios a lot cleaner to implement.
因此， comparing()和thenComparing()肯定会使更复杂的排序场景的实现变得更干净。
9. Conclusion
9.结语
In this article, we saw how we can apply sorting to Array, List, Set, and Map.
在这篇文章中，我们看到了如何对Array、List、Set和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.
文章中使用的所有例子都可以在GitHub上找到over。