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

Question

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

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

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

Answer 1

Guava предоставляет эту функциональность через класс Ordering . Ordering - это Comparator ++. В этом случае, если у вас есть список некоторого типа, который реализует Comparable, вы можете написать:

boolean sorted = Ordering.natural().isOrdered(list);

Это работает для любых Iterable, а не только для List, и вы можете легко обработать null s, указав, должны ли они идти до или после любых других не null элементов:

Ordering.natural().nullsLast().isOrdered(list);

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

Ordering.natural().reverse().isOrdered(list);

Пользователи Java 8 : вместо этого используйте эквивалент Comparators#isInOrder(Iterable), поскольку остальная часть Ordering в основном устарела (как объяснено в классе документация ).

Answer 2

Вот общий метод, который сделает свое дело:

public static <T extends Comparable<? super T>>
        boolean isSorted(Iterable<T> iterable) {
    Iterator<T> iter = iterable.iterator();
    if (!iter.hasNext()) {
        return true;
    }
    T t = iter.next();
    while (iter.hasNext()) {
        T t2 = iter.next();
        if (t.compareTo(t2) > 0) {
            return false;
        }
        t = t2;
    }
    return true;
}

Answer 3

Легко:

List tmp = new ArrayList(myList);
Collections.sort(tmp);
boolean sorted = tmp.equals(myList);

Или (если элементы сопоставимы):

Object prev;
for( Object elem : myList ) {
    if( prev != null && prev.compareTo(elem) > 0 ) {
        return false;
    }
    prev = elem;
}
return true;

Или (если элементы несопоставимы):

Object prev;
for( Object elem : myList ) {
    if( prev != null && myComparator.compare(prev,elem) > 0 ) {
        return false;
    }
    prev = elem;
}
return true;

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

Answer 4

Если вы используете Java 8, потоки могут помочь.

list.stream().sorted().collect(Collectors.toList()).equals(list);

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

Этот метод может быть не самым быстродействующим решением, но его проще всего реализовать, который не включает сторонние фреймворки.

Answer 5

Чтобы проверить, является ли список или любая структура данных по этому вопросу задачей, которая занимает всего O (n) времени.Просто переберите список с помощью интерфейса Iterator и просмотрите данные (в вашем случае они уже готовы как тип Comparable) от начала до конца, и вы сможете найти, отсортирован ли он или нет

Answer 6

Просто используйте итератор для просмотра содержимого List<T>.

public static <T extends Comparable> boolean isSorted(List<T> listOfT) {
    T previous = null;
    for (T t: listOfT) {
        if (previous != null && t.compareTo(previous) < 0) return false;
        previous = t;
    }
    return true;
}

Answer 7

Если вам это нужно для модульного тестирования, вы можете использовать AssertJ .Он содержит утверждение, чтобы проверить, отсортирован ли список:

List<String> someStrings = ...
assertThat(someStrings).isSorted();

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

Answer 8

private static <T extends Comparable<? super T>> boolean isSorted(List<T> array){
    for (int i = 0; i < array.size()-1; i++) {
        if(array.get(i).compareTo(array.get(i+1))> 0){
            return false;
        }
    }
    return true;
}

zzzzz не уверен, ребята, что вы, ребята, делаете, но это можно сделать в простом цикле for.

Answer 9

Вот что я бы сделал:

public static <T extends Comparable<? super T>> boolean isSorted(List<T> list) {
    if (list.size() != 0) {
        ListIterator<T> it = list.listIterator();
        for (T item = it.next(); it.hasNext(); item = it.next()) {
            if (it.hasPrevious() && it.previous().compareTo(it.next()) > 0) {
                return false;
            }
        }

    }
    return true;
}

Answer 10

Это операция, которая займет O (n) время (наихудший случай). Вам нужно будет обработать два случая: когда список отсортирован в порядке убывания, и где список отсортирован в порядке возрастания.

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