Итераторы списка гарантируют, прежде всего, что вы получите элементы списка во внутреннем порядке списка (он же. порядок вставки ). Точнее, в том порядке, в котором вы вставили элементы, или о том, как вы манипулировали списком. Сортировка может рассматриваться как манипулирование структурой данных, и существует несколько способов сортировки списка.
Я закажу пути в порядке полезности , как я лично это вижу:
1. Попробуйте использовать Set или Bag коллекций вместо
ПРИМЕЧАНИЕ: Я поставил эту опцию сверху, потому что это то, что вы обычно хотите делать в любом случае.
Сортированный набор автоматически сортирует коллекцию при вставке , что означает, что она выполняет сортировку при добавлении элементов в коллекцию. Это также означает, что вам не нужно сортировать вручную.
Кроме того, если вы уверены, что вам не нужно беспокоиться о (или иметь) дубликаты элементов, вы можете вместо этого использовать TreeSet<T>. Он реализует интерфейсы SortedSet и NavigableSet и работает так, как вы, вероятно, ожидаете из списка:
TreeSet<String> set = new TreeSet<String>();
set.add("lol");
set.add("cat");
// automatically sorts natural order when adding
for (String s : set) {
System.out.println(s);
}
// Prints out "cat" and "lol"
Если вы не хотите естественного упорядочения, вы можете использовать параметр конструктора, который принимает Comparator<T>.
В качестве альтернативы, вы можете использовать Multisets (также известный как Bags ) , то есть Set, который позволяет дублировать элементы, вместо этого есть и третий Партийные реализации их. В частности, из библиотек Guava есть TreeMultiset, который работает так же, как TreeSet.
2. Сортируйте ваш список с Collections.sort()
Как упоминалось выше, сортировка List s - это манипулирование структурой данных. Так что для ситуаций, когда вам нужен «один источник правды», который будет отсортирован различными способами, тогда сортировка вручную - это путь.
Вы можете отсортировать свой список с помощью метода java.util.Collections.sort(). Вот пример кода о том, как:
List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");
Collections.sort(strings);
for (String s : strings) {
System.out.println(s);
}
// Prints out "cat" and "lol"
Использование компараторов
Одно очевидное преимущество заключается в том, что вы можете использовать Comparator в методе sort. Java также предоставляет некоторые реализации для Comparator, такие как Collator, который полезен для чувствительных к локали строк сортировки. Вот один пример:
Collator usCollator = Collator.getInstance(Locale.US);
usCollator.setStrength(Collator.PRIMARY); // ignores casing
Collections.sort(strings, usCollator);
Сортировка в параллельных средах
Обратите внимание, что использование метода sort недопустимо в параллельных средах, поскольку экземпляром коллекции будет манипулировать, и вам следует рассмотреть возможность использования неизменяемых коллекций. Это то, что Гуава предоставляет в классе Ordering и представляет собой простую однострочную строку:
List<string> sorted = Ordering.natural().sortedCopy(strings);
3. Сверните список java.util.PriorityQueue
Хотя в Java нет отсортированного списка, тем не менее, есть отсортированная очередь, которая, вероятно, сработает для вас. Это java.util.PriorityQueue класс.
Нико Хаазе в комментариях связался с связанным вопросом , который также отвечает на этот вопрос.
В отсортированной коллекции вы, скорее всего, не хотите манипулировать внутренней структурой данных, поэтому PriorityQueue не реализует интерфейс List (потому что это даст вам прямой доступ к его элементам).
Предупреждение об итераторе PriorityQueue
Класс PriorityQueue реализует интерфейсы Iterable<E> и Collection<E>, поэтому его можно повторять как обычно. Однако итератор не гарантирует возвращение элементов в отсортированном порядке. Вместо этого (как указывает Альдерат в комментариях) вам нужно poll() очередь, пока она не опустеет.
Обратите внимание, что вы можете преобразовать список в приоритетную очередь с помощью конструктора , который принимает любую коллекцию :
List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");
PriorityQueue<String> sortedStrings = new PriorityQueue(strings);
while(!sortedStrings.isEmpty()) {
System.out.println(sortedStrings.poll());
}
// Prints out "cat" and "lol"
4. Напишите свой SortedList класс
ПРИМЕЧАНИЕ: Вам не нужно этого делать.
Вы можете написать свой собственный класс List, который сортирует каждый раз, когда вы добавляете новый элемент. Это может привести к довольно сложным вычислениям в зависимости от вашей реализации и будет бессмысленным , если только вы не захотите сделать это в качестве упражнения по двум основным причинам:
- Это нарушает контракт, который есть у интерфейса
List<E>, потому что методы add должны гарантировать, что элемент будет находиться в указанном пользователем индексе. - Зачем изобретать колесо?Вместо этого вы должны использовать TreeSet или Multisets, как указано в первом пункте выше.
Однако, если вы хотите сделать это в качестве упражнения, здесь приведен пример кода для начала, он используетAbstractList абстрактный класс:
public class SortedList<E> extends AbstractList<E> {
private ArrayList<E> internalList = new ArrayList<E>();
// Note that add(E e) in AbstractList is calling this one
@Override
public void add(int position, E e) {
internalList.add(e);
Collections.sort(internalList, null);
}
@Override
public E get(int i) {
return internalList.get(i);
}
@Override
public int size() {
return internalList.size();
}
}
Обратите внимание, что если вы не переопределили нужные вам методы, то реализации по умолчанию из AbstractList будут выбрасывать UnsupportedOperationException s.