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

Answer 2

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

Answer 3

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

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

Answer 4

Easy:

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 5

Просто используйте итератор, чтобы просмотреть содержимое 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 6

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

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 7

Вот общий метод, который будет делать трюк:

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 8

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

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

Answer 9

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

Answer 10

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

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

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

Answer 11

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

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

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

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