1. Обзор
В этой статье показано, как применить сортировку к Array , List , Set и Map в 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 использует двойную сводную быструю сортировку для примитивов . Он предлагает производительность O(n log(n)) и, как правило, быстрее, чем традиционные (одноповоротные) реализации Quicksort. Однако он использует стабильную, адаптивную, итеративную реализацию алгоритма сортировки слиянием для Array of Objects .
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 — с сигнатурой, аналогичной API 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 , это всего лишь вопрос использования многопоточности.
Наконец, есть похожие варианты API Arrays.sort в Arrays.parallelSort :
Arrays.parallelSort (int [] a, int fromIndex, int toIndex);
3. Сортировка списка
Давайте теперь воспользуемся API Collections.sort() в java.utils.Collections — для сортировки списка целых чисел:
@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 , он использует модифицированную сортировку слиянием и обеспечивает гарантированную производительность n log(n) .
4. Сортировка набора
Далее воспользуемся Collections.sort() для сортировки LinkedHashSet .
Мы используем LinkedHashSet , потому что он поддерживает порядок вставки.
Обратите внимание, что для использования 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. Карта сортировки
В этом разделе мы начнем рассматривать сортировку карты — как по ключам, так и по значениям.
Давайте сначала определим карту, которую мы будем сортировать:
@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]
Карта после сортировки по значениям :
[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
}
Мы будем использовать следующий массив сотрудников для примера сортировки в следующих разделах:
@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 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());
}
}
В общем случае логика для сравнения будет написана методом compareTo . Здесь мы сравниваем заказ сотрудника или имя поля сотрудника. Два сотрудника будут равны, если у них одинаковое имя.
Теперь, когда Arrays.sort(сотрудники); вызывается в приведенном выше коде, теперь мы знаем, какова логика и порядок сортировки сотрудников по возрасту:
[("Earl", 43, 10000),("Frank", 33, 70000), ("Jessica", 23, 4000),
("John", 23, 5000),("Pearl", 33, 4000), ("Steve", 26, 6000)]
Мы видим, что массив отсортирован по имени сотрудника, что теперь становится естественным порядком для класса сотрудников .
6.2. Использование компаратора
Теперь давайте отсортируем элементы, используя реализацию интерфейса Comparator , где мы на лету передаем анонимный внутренний класс API Arrays.sort() :
@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());
}
});
Отсортированные массивы Employees на основе зарплаты будут:
[(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. Сортировка с помощью лямбда-выражений
Начните с Java 8, мы можем использовать Lambdas для реализации функционального интерфейса компаратора .
Вы можете ознакомиться с записью Lambdas в Java 8 , чтобы освежить в памяти синтаксис.
Заменим старый компаратор:
Comparator<Integer> c = new Comparator<>() {
@Override
public int compare(Integer a, Integer b) {
return Integer.compare(a, b);
}
}
С эквивалентной реализацией, используя лямбда-выражение:
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-интерфейсами, полезными для сортировки, — Compare( ) и 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 , реализующего функциональный интерфейс с функцией сравнения.
Вот массив сотрудников после сортировки:
[(John,23,5000.0), (Jessica,23,4000.0), (Steve,26,6000.0), (Frank,33,7000.0),
(Pearl,33,6000.0), (Earl,43,10000.0)]
Здесь сотрудники отсортированы по возрасту .
Мы видим, что Джон и Джессика одного возраста — это означает, что логика заказа теперь должна учитывать их имена — чего мы можем добиться с помощью 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)
]
Таким образом , compare( ) и thenComparing() определенно упрощают реализацию более сложных сценариев сортировки.
9. Заключение
В этой статье мы увидели, как мы можем применить сортировку к Array , List , Set и Map .
Мы также увидели краткое введение о том, как функции Java 8 могут быть полезны при сортировке, такие как использование лямбда-выражений, Compare () и thenComparing() и parallelSort() .
Все примеры, использованные в статье, доступны на GitHub .