Java中的排序
1.概述
本文將說明如何在Java 7和Java 8中對Array ， List ， Set和Map進行排序。
2.用數組排序
讓我們首先使用*Arrays.sort（）方法對整數數組進行排序*。
我們將在*@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。排序完整數組
現在讓我們使用簡單的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對原語使用雙軸Quicksort。它提供O（n log（n））性能，並且通常比傳統的（單軸）Quicksort實現更快。但是，它使用對 像數組的mergesort算法的穩定，自適應，迭代實現。
2.2。排序數組的一部分
Arrays.sort還有另外一種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（） API類似：
@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中也有API Arrays.sort的類似變體：
Arrays.parallelSort (int [] a, int fromIndex, int toIndex);3.排序列表
現在讓我們使用*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)));
}排序之前的列表將包含以下元素：
[5, 1, 89, 255, 7, 88, 200, 123, 66]並且自然地，在排序之後：
[1, 5, 7, 66, 88, 89, 123, 200, 255]如Oracle JavaDoc for Collections.Sort中所述，它使用了經過修改的mergesort並提供了保證的n log（n）性能。
4.排序集
接下來，讓我們使用*Collections.sort（）對LinkedHashSet*進行排序。
我們使用LinkedHashSet，因為它維護插入順序。
請注意，為了在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()));
}*Comparator.reverseOrder（）*方法可逆轉自然排序所施加的排序。
5.排序圖
在本節中，我們將開始研究按鍵和值對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。按鍵對地圖排序
現在，在此示例中，我們將從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不能保證鍵的順序）。
排序前的地圖：
[Key: 66 , Value: Earl]
[Key: 22 , Value: Apple]
[Key: 6 , Value: Rocky]
[Key: 55 , Value: John]
[Key: 12 , Value: George]
[Key: 77 , Value: Pearl]按鍵排序後的地圖：
[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。按值對地圖排序
在這裡，我們將比較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));
}排序前的地圖：
[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) {
...
}
// standard getters, setters and toString
}在以下各節中，我們將使用以下Employee Array進行排序的示例：
@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)};
}我們可以對自定義對象的數組或集合進行排序：
- 以自然順序（使用可比接口）或
- 按照比較器**界面提供的順序
6.1。使用可比
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（）方法，用於比較當前對象和作為參數傳遞的對象。
為了清楚地理解這一點，讓我們看一個示例Employee類，該類實現Comparable接口：
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方法。在這裡，我們正在比較員工訂單或員工姓名。如果兩名僱員的姓名相同，則他們是平等的。
現在當*Arrays.sort（employees）;*在上面的代碼中稱為，我們現在知道按年齡對員工進行排序的邏輯和順序是什麼：
[("Earl", 43, 10000),("Frank", 33, 70000), ("Jessica", 23, 4000),
("John", 23, 5000),("Pearl", 33, 4000), ("Steve", 26, 6000)]我們可以看到該數組是按員工姓名排序的，這現在成為Employee Class的自然順序。
6.2。使用比較器
現在，讓我們使用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)));
}現在，讓我們根據薪水對員工進行排序-並傳遞另一個比較器實現：
Arrays.sort(employees, new Comparator<Employee>() {
@Override
public int compare(Employee o1, Employee o2) {
return Double.compare(o1.getSalary(), o2.getSalary());
}
});根據薪水排序的僱員數組將是：
[(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（） ，以自然或自定義順序對列表和對象集進行排序，如上面對數組所述。
7.用Lambda排序
從Java 8開始，我們可以使用Lambdas實現比較器功能接口。
您可以看一下Java 8中的Lambda，以了解語法。
讓我們替換舊的比較器：
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自帶的排序有用的兩個新的API - 比較（）和thenComparing（）在Comparator接口。
這些對於鏈接比較器的多個條件非常方便。
讓我們考慮一個場景，在該場景中，我們可能希望按年齡然後按名稱比較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功能的功能接口。
這是排序後的Employees數組：
[(John,23,5000.0), (Jessica,23,4000.0), (Steve,26,6000.0), (Frank,33,7000.0),
(Pearl,33,6000.0), (Earl,43,10000.0)]這裡的員工是按年齡分類的。
我們可以看到John和Jessica年齡相同–這意味著順序邏輯現在應該考慮到它們的名稱–我們可以使用thenComparing（）實現：
...
employees.sort(Comparator.comparing(Employee::getAge)
.thenComparing(Employee::getName));
...
使用上面的代碼片段進行排序後，employee數組中的元素將被排序為：
[(Jessica,23,4000.0),
(John,23,5000.0),
(Steve,26,6000.0),
(Frank,33,7000.0),
(Pearl,33,6000.0),
(Earl,43,10000.0)
]因此， compare （）和thenComparing（）無疑使更複雜的排序方案更加清晰地實現。
9.結論
在本文中，我們看到瞭如何對Array ， List ， Set和Map進行排序。
我們還簡要介紹了Java 8的功能如何在排序中有用，例如使用Lambda， comparing（），然後Comparing（）和parallelSort（） 。
本文中使用的所有示例都可以在GitHub上找到。