«Проверка сортировки списка в Java»

«1. Обзор

В этом руководстве мы рассмотрим различные способы проверки сортировки списка в Java.

2. Итеративный подход

Итеративный подход — это простой и интуитивно понятный способ проверки отсортированного списка. В этом подходе мы будем повторять список и сравнивать соседние элементы. Если какой-либо из двух соседних элементов не отсортирован, мы можем сказать, что список не отсортирован.

Список может быть отсортирован как в естественном, так и в пользовательском порядке. Мы рассмотрим оба этих случая, используя интерфейсы Comparable и Comparator.

2.1. Использование Comparable

Во-первых, давайте рассмотрим пример списка, элементы которого имеют тип Comparable. Здесь мы рассмотрим список, содержащий объекты типа String:

public static boolean isSorted(List<String> listOfStrings) {
    if (isEmpty(listOfStrings) || listOfStrings.size() == 1) {
        return true;
    }

    Iterator<String> iter = listOfStrings.iterator();
    String current, previous = iter.next();
    while (iter.hasNext()) {
        current = iter.next();
        if (previous.compareTo(current) > 0) {
            return false;
        }
        previous = current;
    }
    return true;
}

2.2. Использование Comparator

Теперь давайте рассмотрим класс Employee, который не реализует Comparable. Итак, в этом случае нам нужно использовать Компаратор для сравнения соседних элементов списка:

public static boolean isSorted(List<Employee> employees, Comparator<Employee> employeeComparator) {
    if (isEmpty(employees) || employees.size() == 1) {
        return true;
    }

    Iterator<Employee> iter = employees.iterator();
    Employee current, previous = iter.next();
    while (iter.hasNext()) {
        current = iter.next();
        if (employeeComparator.compare(previous, current) > 0) {
            return false;
        }
        previous = current;
    }
    return true;
}

Приведенные выше два примера похожи. Единственная разница заключается в том, как мы сравниваем предыдущий и текущий элементы списка.

Кроме того, мы также можем использовать Компаратор, чтобы иметь точный контроль над проверкой сортировки. Дополнительная информация об этих двух доступна в нашем учебнике Comparator and Comparable in Java.

3. Рекурсивный подход

Теперь мы посмотрим, как проверить отсортированный список с помощью рекурсии:

public static boolean isSorted(List<String> listOfStrings) {
    return isSorted(listOfStrings, listOfStrings.size());
}

public static boolean isSorted(List<String> listOfStrings, int index) {
    if (index < 2) {
        return true;
    } else if (listOfStrings.get(index - 2).compareTo(listOfStrings.get(index - 1)) > 0) {
        return false;
    } else {
        return isSorted(listOfStrings, index - 1);
    }
}

4. Использование Guava

Вместо этого часто лучше использовать стороннюю библиотеку написания собственной логики. В библиотеке Guava есть несколько служебных классов, которые мы можем использовать для проверки сортировки списка.

4.1. Класс сортировки Guava

В этом разделе мы увидим, как использовать класс Ordering в Guava для проверки отсортированного списка.

Сначала мы рассмотрим пример списка, содержащего элементы типа Comparable:

public static boolean isSorted(List<String> listOfStrings) {
    return Ordering.<String> natural().isOrdered(listOfStrings);
}

Далее мы увидим, как мы можем проверить, отсортирован ли список объектов Employee с помощью Comparator: ~~ ~

public static boolean isSorted(List<Employee> employees, Comparator<Employee> employeeComparator) {
    return Ordering.from(employeeComparator).isOrdered(employees);
}

Кроме того, мы можем использовать функцию natural().reverseOrder(), чтобы проверить, отсортирован ли список в обратном порядке. Кроме того, мы можем использовать natural().nullFirst() и natural().nullLast(), чтобы проверить, появляется ли null первым или последним в отсортированном списке.

Чтобы узнать больше о классе Guava Ordering, мы можем обратиться к нашему Руководству по статье Guava’s Ordering.

4.2. Класс компараторов Guava

Если мы используем Java 8 или выше, Guava предоставляет лучшую альтернативу с точки зрения класса Comparators. Мы увидим пример использования метода isInOrder этого класса:

public static boolean isSorted(List<String> listOfStrings) {
    return Comparators.isInOrder(listOfStrings, Comparator.<String> naturalOrder());
}

Как мы видим, в приведенном выше примере мы использовали естественный порядок для проверки отсортированного списка. Мы также можем использовать компаратор для настройки проверки сортировки.

5. Заключение

В этой статье мы увидели, как мы можем проверить отсортированный список, используя простой итеративный подход, рекурсивный подход и использование Guava. Мы также кратко коснулись использования Comparator и Comparable при определении логики проверки сортировки.

Реализацию всех этих примеров и фрагментов кода можно найти на GitHub.