Iteratory list gwarantują przede wszystkim, że elementy listy są uporządkowane wewnętrznie (np. Kolejność wstawiania ). Mówiąc dokładniej, jest to w kolejności wstawiania elementów lub sposobu manipulowania listą. Sortowanie może być postrzegane jako manipulacja strukturą danych i istnieje kilka sposobów sortowania listy.
Zamienię sposoby w kolejności użyteczności, tak jak ja to widzę:
1. Zastanów się nad użyciem Setlub Bagkolekcjami
UWAGA: Umieszczam tę opcję na górze, ponieważ i tak zwykle chcesz to zrobić.
Posortowany zestaw automatycznie sortuje kolekcję przy wstawianiu , co oznacza, że wykonuje sortowanie podczas dodawania elementów do kolekcji. Oznacza to również, że nie trzeba go ręcznie sortować.
Ponadto, jeśli masz pewność, że nie musisz się martwić (lub mieć) zduplikowanymi elementami, możesz TreeSet<T>zamiast tego użyć . Implementuje SortedSeti NavigableSetinterfejsy oraz działa tak, jak można się spodziewać po liście:
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"
Jeśli nie chcesz naturalnego uporządkowania, możesz użyć parametru konstruktora, który przyjmuje parametr Comparator<T>.
Alternatywnie możesz użyć Multisets (znanych również jako Torby ) , czyli takich, Setktóre pozwalają na duplikowanie elementów, a są one ich implementacje innych firm. Przede wszystkim z bibliotek Guava istnieje taki TreeMultiset, który działa podobnie jak TreeSet.
2. Posortuj listę za pomocą Collections.sort()
Jak wspomniano powyżej, sortowanie Lists jest manipulacją strukturą danych. Tak więc w sytuacjach, w których potrzebujesz „jednego źródła prawdy”, które zostanie posortowane na różne sposoby, a następnie posortowanie go ręcznie.
Możesz posortować listę za pomocą java.util.Collections.sort()metody. Oto przykładowy kod:
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"
Korzystanie z komparatorów
Jedną z wyraźnych korzyści jest to, że możesz użyć Comparatortej sortmetody. Java zapewnia także pewne implementacje dla Comparatortakich, Collatorktóre są przydatne do łańcuchów sortujących wrażliwych na ustawienia regionalne. Oto jeden przykład:
Collator usCollator = Collator.getInstance(Locale.US);
usCollator.setStrength(Collator.PRIMARY); // ignores casing
Collections.sort(strings, usCollator);
Sortowanie w współbieżnych środowiskach
Należy jednak pamiętać, że użycie tej sortmetody nie jest przyjazne w środowiskach współbieżnych, ponieważ instancja kolekcji zostanie zmanipulowana, a zamiast tego należy rozważyć użycie niezmiennych kolekcji. Jest to coś, co Guava zapewnia w Orderingklasie i jest prostym, jedno-liniowym tekstem:
List<string> sorted = Ordering.natural().sortedCopy(strings);
3. Zawiń listę java.util.PriorityQueue
Chociaż w Javie nie ma posortowanej listy, istnieje jednak posortowana kolejka, która prawdopodobnie będzie dla Ciebie równie dobra. To jest java.util.PriorityQueueklasa.
Nico Haase podał w komentarzach powiązane pytanie, które również na to odpowiada.
W posortowanej kolekcji najprawdopodobniej nie chcesz manipulować wewnętrzną strukturą danych, dlatego PriorityQueue nie implementuje interfejsu List (ponieważ to dałoby ci bezpośredni dostęp do jego elementów).
Zastrzeżenie dotyczące PriorityQueueiteratora
Do PriorityQueueklasy implementuje Iterable<E>i Collection<E>interfejsy więc może należy powtórzyć, jak zwykle. Jednak nie ma gwarancji, że iterator zwróci elementy w posortowanej kolejności. Zamiast tego (jak wskazuje Alderath w komentarzach) musisz stać w poll()kolejce, aż będzie pusty.
Zauważ, że możesz przekonwertować listę do kolejki priorytetowej za pomocą konstruktora, który pobiera dowolną kolekcję :
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. Napisz własną SortedListklasę
UWAGA: Nie powinieneś tego robić.
Możesz napisać własną klasę List, która będzie sortować za każdym razem, gdy dodasz nowy element. Może to być trudne do obliczeń w zależności od implementacji i jest bezcelowe , chyba że chcesz to zrobić jako ćwiczenie, z dwóch głównych powodów:
- Łamie kontrakt, który
List<E>ma interfejs, ponieważ addmetody powinny zapewnić, że element znajdzie się w indeksie określonym przez użytkownika.
- Po co wymyślać koło ponownie? Zamiast tego powinieneś używać TreeSet lub Multisets, jak wskazano w pierwszym punkcie powyżej.
Jeśli jednak chcesz to zrobić jako ćwiczenie, tutaj jest próbka kodu na początek, korzysta z AbstractListklasy abstrakcyjnej:
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();
}
}
Zauważ, że jeśli nie przesłoniłeś potrzebnych metod, wówczas domyślne implementacje z AbstractListwyrzucą UnsupportedOperationExceptions.
