Научитесь проверять, отсортирован ли заданный массив в определенном порядке сортировки, т. е. по возрастанию, по убыванию или в пользовательском порядке.
1. Обзор
Массив считается отсортированным, если каждый элемент массива больше или меньше своего предшественника в зависимости от порядка сортировки массива.
Чтобы найти такую пару элементов, мы должны перебрать все элементы массива и сравнить его со следующим элементом, если он нарушает порядок сортировки, то мы делаем вывод, что массив не отсортирован. В противном случае массив сортируется, если такой пары элементов нет.
Обратите внимание, что порядок сортировки массива можно определить следующими способами:
- Все примитивы сравниваются по их числовым значениям.
- Объекты Java, реализующие интерфейс Comparable, сравниваются на основе предоставленной логики в переопределенном методе compareTo().
- Все остальные объекты Java должны пройти сортировку с помощью экземпляра интерфейса Comparator.
- Для изменения любой логики сравнения на обратную мы всегда можем использовать экземпляр Comparator.reversed().
2. Проверка отсортированного массива
2.1. Примитивные массивы
Чтобы проверить сортировку примитивных массивов, мы должны проверить порядок элементов массива в цикле. Это должно быть сделано либо в порядке возрастания, либо в порядке убывания, в обоих случаях.
- Для проверки возрастающего порядка мы используем noneMatch() API, который возвращает true, если ни один элемент потока не соответствует предоставленному предикату. Обратите внимание, что API может не оценить предикат для всех элементов, если он сможет найти соответствующую пару до достижения конца массива.
- Для проверки порядка убывания используйте API allMatch().
int[] array = { 1, 2, 3, 4, 5 };boolean isSorted = checkIsSortedPrimitiveArrayWithStream(array);System.out.println(isSorted); //truepublic static boolean checkIsSortedPrimitiveArrayWithStream(final int[] array) {if(array == null || array.length <= 1) {return true;}return IntStream.range(0, array.length - 1).noneMatch(i -> array[i] > array[i + 1]);}2.2. Проверка отсортированного массива на сопоставимость объектов
Если объекты, хранящиеся в массиве, реализуют интерфейс Comparable, то мы можем использовать метод compareTo() для проверки равенства объектов при сравнении элементов объектов для естественного упорядочивания.
Integer[] array = { 1, 2, 3, 4, 5 };isSorted = checkIsSortedObjectArrayWithStream(ArrayUtils.toObject(array));System.out.println(isSorted); //truepublic static <T extends Comparable<? super T>>boolean checkIsSortedObjectArrayWithStream(final T[] array) {if(array.length <= 1) {return true;}return IntStream.range(0, array.length - 1).noneMatch(i -> array[i].compareTo(array[i + 1]) > 0);}2.3. Проверка отсортированного массива с помощью компаратора
Если элементы массива не реализуют интерфейс Comparable, то для проверки отсортированного массива можно использовать экземпляр Comparator.
User[] users = getSortedArray();Comparator<User> firstNameSorter = Comparator.comparing(User::firstName);isSorted = checkIsSortedObjectArrayForCustomSort(users, firstNameSorter);System.out.println(isSorted); //truepublic static <T> boolean checkIsSortedObjectArrayForCustomSort(final T[] array, final Comparator<T> comparator) {if(comparator == null) {throw new IllegalArgumentException("Comparator should not be null.");}if(array.length <= 1) {return true;}return IntStream.range(0, array.length - 1).noneMatch(i -> comparator.compare(array[i], array[i + 1]) > 0);}3. ArrayUtils от Apache Commons
Все вышеперечисленные методы были в основном предназначены для того, чтобы вы поняли, как проверяются отсортированные массивы. Класс org.apache.commons.lang3.ArrayUtils из Apache Common содержит метод isSorted(), который может выполнять все вышеперечисленные сравнения в одной строке.
User[] users = getSortedArray();isSorted = ArrayUtils.isSorted(array); //Natural orderSystem.out.println(isSorted); //trueisSorted = ArrayUtils.isSorted(array,Comparator.comparing(User::firstName)); //Custom orderSystem.out.println(isSorted); //true
4. Заключение
В этом уроке Java мы научились проверять, отсортирован ли уже заданный массив. Мы научились определять характер сортировки для массива примитивов, массива объектов Comparable и массива объектов, которые не реализуют Comparable.
Неважно, какую технику мы выберем, логика останется прежней. Поэтому желательно использовать класс ArrayUtils из Apache Commons, чтобы избежать переписывания этой простой логики.