1. Огляд
Ця стаття проілюструє, як застосувати сортування до масиву , списку , набору та карти в Java 7 та Java 8.
2. Сортування за масивом
Почнемо із сортування цілочисельних масивів спочатку за допомогою методу Arrays.sort () .
Ми визначимо такі масиви int у методі @Before jUnit:
@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. Сортування повного масиву
Давайте тепер використаємо простий API Array.sort () :
@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. Однак він використовує стабільну, адаптивну, ітераційну реалізацію алгоритму злиття для масиву об'єктів.
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 () API:
@Test public void givenIntArray_whenUsingParallelSort_thenArraySorted() { Arrays.parallelSort(toSort); assertTrue(Arrays.equals(toSort, sortedInts)); }За лаштунками паралельного сортування () він розбиває масив на різні підмасиви (відповідно до деталізації в алгоритмі паралельного сортування ). Кожен підмасив сортується за допомогою Arrays.sort () у різних потоках, так що сортування може виконуватися паралельно і об'єднується остаточно як відсортований масив.
Зверніть увагу, що спільний пул ForJoin використовується для виконання цих паралельних завдань, а потім злиття результатів.
Результат Arrays.parallelSort буде таким самим, як і Array.sort, звичайно, це лише питання використання багатопоточності.
Нарешті, у Arrays.parallelSort також є подібні варіанти API Arrays.sort :
Arrays.parallelSort (int [] a, int fromIndex, int toIndex);3. Сортування списку
Давайте тепер використаємо API Collections.sort () у java.utils.Collections - для сортування списку цілих чисел:
@Test public void givenList_whenUsingSort_thenSortedList() { List 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 , він використовує модифікований метод злиття та пропонує гарантовану продуктивність n журналу (n) .
4. Сортування набору
Далі, давайте використаємо Collections.sort () для сортування LinkedHashSet .
Ми використовуємо LinkedHashSet, оскільки він підтримує порядок вставки.
Зверніть увагу, що для того, щоб використовувати API сортування у колекціях - ми спочатку обертаємо набір у список :
@Test public void givenSet_whenUsingSort_thenSortedSet() { Set integersSet = new LinkedHashSet(Ints.asList(toSort)); Set descSortedIntegersSet = new LinkedHashSet( Arrays.asList(new Integer[] {255, 200, 123, 89, 88, 66, 7, 5, 1})); List list = new ArrayList(integersSet); Collections.sort(Comparator.reverseOrder()); integersSet = new LinkedHashSet(list); assertTrue(Arrays.equals( integersSet.toArray(), descSortedIntegersSet.toArray())); }Метод Comparator.reverseOrder () змінює порядок, накладений природним упорядкуванням.
5. Карта сортування
У цьому розділі ми почнемо розглядати сортування карти - як за ключами, так і за значеннями.
Давайте спочатку визначимо карту, яку ми будемо сортувати:
@Before public void initVariables () { .... HashMap 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. Сортування карти за клавішами
We'll now extract keys and values entries from the HashMap and sort it based on the values of the keys in this example:
@Test public void givenMap_whenSortingByKeys_thenSortedMap() { Integer[] sortedKeys = new Integer[] { 6, 12, 22, 55, 66, 77 }; List
entries = new ArrayList(map.entrySet()); Collections.sort(entries, new Comparator
() { @Override public int compare( Entry o1, Entry o2) { return o1.getKey().compareTo(o2.getKey()); } }); Map sortedMap = new LinkedHashMap(); for (Map.Entry 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:
[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:
@Test public void givenMap_whenSortingByValues_thenSortedMap() { String[] sortedValues = new String[] { "Apple", "Earl", "George", "John", "Pearl", "Rocky" }; List
entries = new ArrayList(map.entrySet()); Collections.sort(entries, new Comparator
() { @Override public int compare( Entry o1, Entry o2) { return o1.getValue().compareTo(o2.getValue()); } }); Map sortedMap = new LinkedHashMap(); for (Map.Entry 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:
@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 ComparatorInterface
6.1. Using Comparable
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.
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.
To understand this clearly, let's see an example Employee class which implements Comparable Interface:
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.
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:
@Test public void givenIntegerArray_whenUsingSort_thenSortedArray() { Integer [] integers = ArrayUtils.toObject(toSort); Arrays.sort(integers, new Comparator() { @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:
Arrays.sort(employees, new Comparator() { @Override public int compare(Employee o1, Employee o2) { return Double.compare(o1.getSalary(), 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.
You can have a look at the Lambdas in Java 8 writeup to brush up on the syntax.
Let's replace the old comparator:
Comparator c = new Comparator() { @Override public int compare(Integer a, Integer b) { return Integer.compare(a, b); } }With the equivalent implementation, using Lambda expression:
Comparator 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
Java 8 comes with two new APIs useful for sorting – comparing() and thenComparing() in the Comparator interface.
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:
@Test public void givenArrayObjects_whenUsingComparing_thenSortedArrayObjects() { List 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.
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():
... 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.
9. Conclusion
In this article, we saw how we can apply sorting to Array, List, Set, and Map.
Ми також побачили короткий вступ про те, як функції Java 8 можуть бути корисними при сортуванні, як використання Lambdas, порівняння (), а потім Порівняння () та паралельногоСортування () .
Усі приклади, використані в статті, доступні на GitHub.