Jak poprawnie sortować w Javie

Analizując kod źródłowy wielu projektów Java typu open source, odkryłem, że większość programistów implementuje sortowanie tylko na dwa różne sposoby. Jedna z nich opiera się na wykorzystaniu metody sort()klasowej Collectionsor Arrays, a druga na wykorzystaniu samosortujących się struktur danych takich jak TreeMapand TreeSet.

Korzystanie z metody sort().

Jeśli chcesz posortować kolekcję, użyj metody Collections.sort().

// Collections.sort(…)
List<ObjectName> list = new ArrayList<ObjectName>();
Collections.sort(list, new Comparator<ObjectName>() {
	public int compare(ObjectName o1, ObjectName o2) {
		return o1.toString().compareTo(o2.toString());
	}
});

Jeśli chcesz posortować tablicę, użyj metody Arrays.sort().

// Arrays.sort(…)
ObjectName[] arr = new ObjectName[10];
Arrays.sort(arr, new Comparator<ObjectName>() {
	public int compare(ObjectName o1, ObjectName o2) {
		return o1.toString().compareTo(o2.toString());
	}
});

Metoda sort()jest bardzo wygodna, gdy kolekcja lub tablica jest już wypełniona wartościami.

Korzystanie z samosortujących się struktur danych

Jeśli chcesz posortować listę ( List) lub zbiór ( Set), użyj TreeSetstruktury sortowania.

// TreeSet
Set<ObjectName> sortedSet = new TreeSet<ObjectName>(new Comparator<ObjectName>() {
	public int compare(ObjectName o1, ObjectName o2) {
		return o1.toString().compareTo(o2.toString());
	}
});
sortedSet.addAll(unsortedSet);

Jeśli chcesz posortować słownik ( Map), użyj TreeMapstruktury sortującej. TreeMapposortowane według klucza ( key).

// TreeMap – использующий String ключи и компаратор (Comparator) CASE_INSENSITIVE_ORDER,
// упорядочивающий строки (String) методом compareToIgnoreCase
Map<String, Integer> sortedMap = new TreeMap<String, Integer>(String.CASE_INSENSITIVE_ORDER);
sortedMap.putAll(unsortedMap);

//TreeMap – общий случай, компаратор указывается вручную
Map<ObjectName, String> sortedMap = new TreeMap<ObjectName, String>(new Comparator<ObjectName>() {
	public int compare(ObjectName o1, ObjectName o2) {
		return o1.toString().compareTo(o2.toString());
	}
});
sortedMap.putAll(unsortedMap);

Powyższe podejście jest bardzo przydatne w przypadkach, gdy trzeba wykonać dużą liczbę wyszukiwań elementów w kolekcji. Samosortujące się struktury danych mają O(log(n))lepszą wydajność niż O(n). Oznacza to, że gdy ilość danych w zbiorze podwoi się, czas wyszukiwania nie podwoi się, ale zwiększy się o stałą wartość .

Złe podejście do problemu sortowania

Nadal można znaleźć przykłady, w których programiści niezależnie opisują algorytmy sortowania. Rozważ kod sortujący przedstawiony poniżej (sortowanie podwójnej tablicy w kolejności rosnącej ). Kod ten jest nie tylko nieefektywny, ale i nieczytelny. A takich przykładów jest wiele.

double t;
for (int i = 0; i < N; i++)
	for (int j = i + 1; j < N; j++)
		if (r[j] < r[i]) {
			t = r[i];
			r[i] = r[j];
			r[j] = t;
		}