Мне нужен метод, который принимает List<T>, где T реализует Comparable и возвращает true или false в зависимости от того, отсортирован ли список или нет.
Каков наилучший способ реализовать это на Java? Очевидно, что дженерики и подстановочные знаки предназначены для работы с такими вещами легко, но я все запутался.
Было бы неплохо иметь аналогичный метод, чтобы проверить, находится ли список в обратном порядке.
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), поскольку остальная часть порядка в основном устарела (как объясняется в классе документация).
Вот общий метод, который сделает трюк:
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;
}
Легко:
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;
Реализации не выполняются для списков, содержащих нулевые значения. Вы должны добавить соответствующие проверки в этом случае.
Если вы используете Java 8, потоки могут помочь.
list.stream().sorted().collect(Collectors.toList()).equals(list);
Этот код сортирует список неуместно и собирает его элементы в другом списке, который затем сравнивается с исходным списком. Сравнение будет успешным, если оба списка содержат одинаковые элементы в равных позициях.
Этот метод может быть не самым быстродействующим решением, но его проще всего реализовать, что не связано с сторонними структурами.
Чтобы проверить, является ли список или какая-либо структура данных в этом случае задачей, которая занимает только время O (n). Просто перебирайте список с помощью интерфейса Iterator и пропустите данные (в вашем случае вы уже имеете его готовый как тип Comparable) от начала до конца, и вы можете узнать, отсортирован ли он или нет.
Просто используйте итератор, чтобы просмотреть содержимое 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;
}
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 не уверен, ребята, что вы делаете, но это можно сделать в простой для цикла.
Если вам это нужно для модульного тестирования, вы можете использовать AssertJ. Он содержит утверждение для проверки сортировки списка:
List<String> someStrings = ...
assertThat(someStrings).isSorted();
Существует также альтернативный метод isSortedAccordingTo, который принимает компаратор, если вы хотите использовать собственный сортировщик для сортировки.
Это операция, которая займет время O (n) (наихудший случай). Вам нужно будет обрабатывать два случая: где список сортируется в порядке убывания и где список сортируется в порядке возрастания.
Вам нужно будет сравнить каждый элемент со следующим элементом, убедившись, что порядок сохранен.
Это то, что я сделал бы:
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(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;
}
Вот метод, использующий 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());
}
Использование потоков 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;