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

1. Обзор

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

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

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

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

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

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

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

    Iterator 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. Использование компаратора

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

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

    Iterator 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;
}

Вышеуказанные два примера схожи. Разница лишь в том, как мы сравниваем предыдущие и текущие элементы списка.

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

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

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

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

public static boolean isSorted(List 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. Класс заказа Гуавы

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

Во-первых, мы увидим пример списка, содержащего элементы типа Сопоставимые :

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

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

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

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

Чтобы узнать больше о Гуава Заказ класса, мы можем направить нашу Путеводитель по заказу Гуавы статья.

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

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

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

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

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

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

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