So sortieren Sie in Java richtig

Bei der Analyse des Quellcodes vieler Open-Source-Java-Projekte habe ich festgestellt, dass die meisten Entwickler die Sortierung nur auf zwei verschiedene Arten implementieren. Eine davon basiert auf der Verwendung der sort()Klassenmethode Collectionsor Arrays, die andere auf der Verwendung selbstsortierender Datenstrukturen wie TreeMapund TreeSet.

Verwendung der Methode sort()

Wenn Sie eine Sammlung sortieren müssen, verwenden Sie die 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());
	}
});

Wenn Sie ein Array sortieren müssen, verwenden Sie die 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());
	}
});

Die Methode sort()ist sehr praktisch, wenn die Sammlung oder das Array bereits mit Werten gefüllt ist.

Verwendung selbstsortierender Datenstrukturen

ListWenn Sie eine Liste ( ) oder einen Satz ( ) sortieren müssen Set, verwenden Sie eine TreeSetSortierstruktur.

// 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);

Wenn Sie ein Wörterbuch ( ) sortieren müssen Map, verwenden Sie eine TreeMapSortierstruktur. TreeMapsortiert nach Schlüssel ( 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);

Der obige Ansatz ist sehr nützlich in Fällen, in denen Sie eine große Anzahl von Suchvorgängen nach Elementen in einer Sammlung durchführen müssen. Selbstsortierende Datenstrukturen haben eine O(log(n))bessere Effizienz als O(n). Das heißt, wenn sich die Datenmenge in der Sammlung verdoppelt, verdoppelt sich die Suchzeit nicht, sondern erhöht sich um einen konstanten Betrag .

Schlechter Ansatz für das Sortierproblem

Es gibt immer noch Beispiele, in denen Programmierer selbstständig Sortieralgorithmen beschreiben. Betrachten Sie den unten dargestellten Sortiercode (Sortieren eines Doppelarrays in aufsteigender Reihenfolge ). Dieser Code ist nicht nur ineffizient, sondern auch unlesbar. Und solche Beispiele gibt es viele.

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;
		}