Научитесь сортировать массив примитивов, строк и пользовательских объектов Java несколькими способами с помощью интерфейсов Comparable и Comparator, API-интерфейсов Arrays.sort() и Stream.sorted().
Мы научимся сортировать массивы в естественном порядке, обратном порядке, а также в любом другом произвольном порядке.
1. Основы сортировки массивов
Основные концепции, лежащие в основе функции сортировки, остаются неизменными независимо от того, какой API Java мы используем для сортировки.
- Все встроенные API поддерживают сортировку с естественным порядком по умолчанию. Числовые типы сортируются в порядке возрастания, строки сортируются в порядке словаря(лексикографически), а пользовательские объекты сортируются в порядке, реализованном интерфейсом Comparable.
- Для сортировки в обратном порядке мы можем использовать Comparator.reverseOrder() для методов сортировки.
- Для сортировки в пользовательском порядке мы должны создать экземпляр интерфейса Comparator и предоставить в нем соответствующее поведение сортировки. Затем мы передадим экземпляр компаратора в API сортировки.
Теперь давайте погрузимся в программы Java, демонстрирующие сортировку массивов. Для пользовательской сортировки мы будем использовать экземпляры класса User. Обратите внимание, что сортировка по умолчанию поддерживается для поля id.
public class User implements Comparable<User> {public long id;public String firstName;public String lastName;//Add getters and setters@Overridepublic int compareTo(final User user) {if(user == null ) {return -1;} else {return(int)(this.id - user.id);}}}2. Arrays.sort() и Arrays.parallelSort()
Класс java.util.Arrays предоставляет множество утилит статических методов. AP-функции sort() также являются такими методами, которые помогают сортировать заданный массив элементов.
Реализация API sort() — это стабильная, адаптивная, итеративная сортировка слиянием, которая требует гораздо меньше, чем n lg(n) сравнений, когда входной массив частично отсортирован. Она обеспечивает производительность традиционной сортировки слиянием, когда входной массив упорядочен случайным образом. Если входной массив почти отсортирован, реализация требует приблизительно n сравнений.
Реализация API parallelSort() представляет собой быструю сортировку с двумя опорными точками, которая обеспечивает производительность O(n log(n)) для всех наборов данных и, как правило, работает быстрее традиционных реализаций быстрой сортировки(с одной опорной точкой).
public static void sort(array, ?comparator)public static void parallelSort(array, ?comparator)
2.1 Сортировка в естественном порядке
Программа Java для сортировки массива String в порядке по умолчанию. Обратите внимание, что класс String уже реализовал интерфейс Comparable.
String[] tokens = {"A","C","B","E","D"};Arrays.sort(tokens); //[A, B, C, D, E]2.2 Сортировка в обратном порядке
Программа на Java, использующая Comparator.reverseOrder() для изменения естественного порядка на обратный.
String[] tokens = {"A","C","B","E","D"};Arrays.sort(tokens, Collections.reverseOrder()); //[E, D, C, B, A]2.3. Пользовательская сортировка
Мы сортируем массив пользователей по их имени.
User[] users = getUsersArray();Comparator firstNameSorter = Comparator.comparing(User::getFirstName);Arrays.sort(users, firstNameSorter);
Для сортировки по нескольким полям, например, для группировки SQL по выражению, мы можем создать сложный экземпляр Comparator и использовать его для сортировки.
Comparator fullNameSorter = Comparator.comparing(Employee::getFirstName).thenComparing(Employee::getLastName);Arrays.sort(employees, fullNameSorter);
3. Сортировка массивов с использованием Stream API
Мы можем отсортировать массив примитивов или пользовательских объектов, используя метод Stream.sorted(), очень похожим образом, как мы использовали API Arrays.sort().
- API sorted() возвращает поток, состоящий из элементов этого потока, отсортированных в естественном порядке.
- Если элементы этого потока не являются Comparable, при выполнении терминальной операции может быть выдано исключение java.lang.ClassCastException.
- Он также принимает необязательный экземпляр компаратора, который используется для реализации пользовательского поведения сортировки.
Для упорядоченных потоков(поток генерируется из упорядоченной коллекции, такой как ArrayList) сортировка стабильна. Для неупорядоченных потоков(например, потоков, генерируемых из HashMap) гарантии стабильности не предоставляются.
Stream<T> sorted()Stream<T> sorted(?comparator)
//1. Natural orderingUser[] sortedUserArray = Stream.of(userArray).sorted().toArray(User[]::new);//2. Reverse orderingUser[] sortedUserArray = Stream.of(userArray).sorted(Comparator.reverseOrder()).toArray(User[]::new);//3. Custom SortingComparator nameComparator = Comparator.comparing(Employee::getName).thenComparing(Employee::getId)User[] sortedUserArray = Stream.of(userArray).sorted(nameComparator).toArray(User[]::new);
4. Заключение
В данном примере мы научились сортировать массив с помощью Arrays.sort() и Stream API. Мы научились сортировать в естественном порядке, обратном порядке, а также в пользовательском порядке.