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

Ответ 1

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

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

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

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

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

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

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

Ответ 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;
}

Ответ 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;

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

Ответ 4

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

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

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

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

Ответ 5

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

Ответ 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;
}

Ответ 7

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

Ответ 8

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

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

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

Ответ 9

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

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

Ответ 10

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

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

Ответ 11

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

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

Ответ 12

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

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

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

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

Ответ 13

Использование потоков Java 8:

boolean isSorted = IntStream.range(1, list.size())
        .map(index -> list.get(index - 1).compareTo(list.get(index)))
        .allMatch(order -> order <= 0);

Это также работает для пустых списков. Однако он эффективен только для списков, в которых также реализован интерфейс маркера RandomAccess (например, ArrayList).

Если у вас нет доступа к потоку, лежащему в основе коллекции, можно использовать следующий уродливый хак:

Stream<T> stream = ...
Comparator<? super T> comparator = ...
boolean isSorted = new AtomicInteger(0) {{
    stream.sequential()
          .reduce((left, right) -> {
               getAndUpdate(order -> (order <= 0) ? comparator.compare(left, right) : order);
               return right;
          });
}}.get() <= 0;