Как определить, отсортирован ли Список в Java?
Я хотел бы метод, который берет a List<T> где T реализации Comparable и возвраты true или false в зависимости от того, отсортирован ли список или нет.
Что лучший способ состоит в том, чтобы реализовать это в Java? Очевидно, что дженерики и подстановочные знаки предназначены, чтобы смочь обработать такие вещи легко, но я получаю все запутанные.
Также было бы хорошо иметь аналогичный метод, чтобы проверить, в обратном порядке ли список.
8 ответов
Guava предоставляет эту функциональность через свой замечательный класс Ordering . Порядок - это Компаратор ++. В этом случае, если у вас есть список некоторого типа, который реализует 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 в основном устарел (как описано в документации по классу ).
Легко:
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;
Реализации не работают для списков, содержащих нулевые значения. В этом случае необходимо добавить соответствующие проверки.
Вот что я бы сделал:
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;
}
Вот общий метод, который подойдет для этой цели:
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;
}
Это операция, которая займет O (n) раз (худший случай). Вам нужно будет обработать два случая: когда список отсортирован в порядке убывания, и где список отсортирован в порядке возрастания.
Вам нужно будет сравнить каждый элемент со следующим элементом, убедившись, что порядок сохраняется.
Одна простая реализация на массивах:
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;
}
Проверить, является ли список или любая структура данных, если на то пошло, - это задача, которая занимает всего O(n) времени. Просто выполните итерацию по списку, используя интерфейс Iterator, и пробегитесь по данным (в вашем случае они уже готовы как тип Comparable) от начала до конца, и вы сможете легко определить, отсортированы они или нет
Просто используйте итератор для просмотра содержимого List .
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;
}