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

1. Обзор

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

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

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

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

2.1. Использование сопоставимых

Во-первых, давайте посмотрим на пример списка, элементы которого имеют тип 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. Использование компаратора

Теперь давайте рассмотрим класс 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 , чтобы иметь точный контроль над проверкой сортировки . Дополнительная информация об этих двух доступна в нашем учебнике 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 есть несколько служебных классов, которые мы можем использовать для проверки сортировки списка.

4.1. Класс заказа гуавы

В этом разделе мы увидим, как использовать класс 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() , чтобы проверить, появляется ли нуль первым или последним в отсортированном списке.

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

4.2. Класс компараторов гуавы

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

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

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

5. Вывод

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

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