In JDK 1.8 lautet die erste Anweisung der Methode java.util.List#sort(Comparator) wie folgt:
Es ist teuer, die Liste in ein Array zu kopieren, zu sortieren und jeden Knoten der Liste auf den sortierten Wert aus dem Array zurückzusetzen.
Es scheint, als wäre es nicht möglich, Werte in ein temporäres Array zu kopieren, wenn ein ArrayList sortiert wird. Habe ich recht? Wenn nicht, was hat die Schöpfer der Methode geführt?
Für ArrayList oder andere Direktzugriffslisten sind Sie möglicherweise richtig.
Collections.sort unterstützt jedoch jede List-Implementierung. Für eine LinkedList zum Beispiel wäre es sehr expansiv gewesen, Elemente während der Sortierung auszutauschen (da das Finden des i-ten Elements lineare Zeit benötigt).
Das Konvertieren der Liste in ein Array und das Festlegen der Elemente der ursprünglichen Liste nach dem Sortieren des Arrays fügt dem Algorithmus eine lineare Zeitkomponente hinzu, die die asymptotische Laufzeit von (O(nlog(n))) nicht ändert.
In OpenJDK 1.8, java.util.ArrayList#sort(Comparator) kopiert nicht das interne Array; es sortiert an Ort und Stelle, wie Sie es vorschlagen sollten.
Die Implementierung von java.util.List#sort() , das Sie kritisieren, enthält die folgende begleitende Dokumentation:
Die Standardimplementierung erhält ein Array, das alle Elemente in dieser Liste enthält, sortiert das Array und iteriert über diese Liste, wobei jedes Element an der entsprechenden Position im Array zurückgesetzt wird. (Dadurch wird die Leistung n² log (n) vermieden, die sich aus dem Versuch ergeben würde, eine verknüpfte Liste an Ort und Stelle zu sortieren.)
Das heißt, das Kopieren des Arrays und das Bewegen mit wahlfreiem Zugriff ist effizienter als der Overhead des linearen Herumschreitens in einer verknüpften Liste. Die übliche Implementierung versucht, kopierten Overhead für den Elementzugriffs-Overhead zu handeln. Für Fälle wie ArrayList , bei denen das Kopieren nicht notwendig ist, um den gleichen wahlfreien Zugriff auf Elemente zu erhalten, wird die Kopie in der Bibliothek durch Überschreiben der Methode weggelassen.
Ein interessanter Vergleich: Schauen Sie sich die Funktionen std::sort() und std::list::sort() der C ++ Standardbibliothek an:
std::sort()
Erfordert Parameter, die einen Bereich mit wahlfreiem Zugriff begrenzen . std::list::sort()
Nimmt nur linearen Zugriff an, indem verknüpfte Listenknoten durchlaufen werden. Der generische std::sort() -Algorithmus ist effizienter, aber die Bibliothek schließt den Aufruf in std::list aus (was eine verkettete Liste ist, ähnlich wie% java.util.LinkedList von Java). Die Bibliothek bietet ein weniger effizientes Mittel zum Sortieren von std::list . Im Gegensatz zur Java-Bibliothek kopiert die C ++ - Bibliothek kein std::list() in ein Array, um den Algorithmus std::sort() mit wahlfreiem Zugriff zu verwenden.