Как определить, отсортирован ли список в Java?

Question

Мне нужен метод, который принимает List<T>, где T реализует Comparable и возвращает true или false в зависимости от того, отсортирован список или нет.

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

Было бы также неплохо иметь аналогичный метод, чтобы проверить, находится ли список в обратном порядке.

Answer 1

Вот метод, использующий Iterable и Comparator.

<T> boolean isSorted(Iterable<? extends T> iterable,
                     Comparator<? super T> comparator) {
    T previous = null;
    for (final T current : iterable) {
        if (previous != null && comparator.compare(previous, current) > 0) {
            return false;
        }
        previous = current;
    }
    return true;
}

И метод для Iterable из Comparable и флаг для упорядочения.

<T extends Comparable<? super T>> boolean isSorted(
        Iterable<? extends T> iterable, boolean natural) {
    return isSorted(iterable, natural ? naturalOrder() : reverseOrder());
}

Answer 2

Одна простая реализация для массивов:

public static <T extends Comparable<? super T>> boolean isSorted(T[] a, int start, int end) {
    while (start<end) {
        if (a[start].compareTo(a[start+1])>0) return false;
        start++;
    }
    return true;
}

Преобразование для списков:

public static <T extends Comparable<? super T>> boolean isSorted(List<T> a) {
    int length=a.size();
    if (length<=1) return true;

    int i=1;
    T previous=a.get(0);
    while (i<length) {
        T current=a.get(i++);
        if (previous.compareTo(current)>0) return false;
        previous=current;
    }
    return true;
}