Frage Warum Collections.sort merge sort statt quicksort? [geschlossen]


Wir wissen, dass schnelle Sortierung der schnellste Sortieralgorithmus ist.

Der collections.sort verwendet den Merge-Sortieralgorithmus anstelle der Schnellsortierung. Aber Arrays.sort verwendet schnelle Sortierung.

Aus welchem ​​Grund verwendet Collections.sort Merge-Sortierung statt Quick-Sortierung?


76
2018-03-01 09:12


Ursprung


Antworten:


Sehr wahrscheinlich von Josh Bloch §:

Ich habe diese Methoden geschrieben, also nehme ich an, dass ich qualifiziert bin zu antworten. Es ist   wahr, dass es keinen einzigen besten Sortieralgorithmus gibt. QuickSort hat   zwei große Mängel im Vergleich zu Mergesort:

  1. Es ist nicht stabil (wie Parsifal bemerkt).

  2. Es tut es nicht Garantie n log n Leistung; es kann sich bei pathologischen Eingaben zu einer quadratischen Leistung verschlechtern.

Stabilität ist für primitive Typen kein Thema, da es keine Vorstellung davon gibt   Identität im Unterschied zur (Wert-) Gleichheit. Und die Möglichkeit von   Das quadratische Verhalten wurde in der Praxis als kein Problem angesehen   Bentely und McIlroy Implementierung (oder später für Doppelter Pivot   Schnelle Sorte), weshalb diese QuickSort - Varianten verwendet wurden   die primitiven Sorten.

Stabilität ist eine große Sache beim Sortieren beliebiger Objekte. Beispielsweise,   Angenommen, Sie haben Objekte, die E-Mail-Nachrichten darstellen, und Sie sortieren   sie zuerst nach Datum, dann nach Absender. Sie erwarten, dass sie sortiert werden   Datum innerhalb jedes Senders, aber das wird nur wahr sein, wenn die Sortierung ist   stabil. Deshalb haben wir uns für eine stabile Sortierung entschieden (Merge Sort)   um Objektverweise zu sortieren. (Technisch gesprochen, mehrfach sequentiell   stabile Sortierungen ergeben eine lexikographische Ordnung auf den Schlüsseln in der   umgekehrte Reihenfolge der Sortierungen: Die endgültige Sortierung bestimmt am meisten   signifikanter Unterschlüssel.)

Es ist ein netter Nebeneffekt, dass Merge Sort Garantien n log n (Zeit)   Leistung, egal was die Eingabe. Natürlich gibt es eine Schattenseite:   quick sort ist eine "in Place" -Sortierung: es benötigt nur log n externen Speicherplatz   (um den Aufrufstapel zu verwalten). Zusammenführen, Sortieren, auf der anderen Seite,   erfordert O (n) externen Raum. Die TimSort-Variante (eingeführt in Java   SE 6) benötigt wesentlich weniger Platz (O (k)), wenn das Eingangsarray ist   fast sortiert.

Auch der Folgendes ist relevant:

Der von java.util.Arrays.sort und (indirekt) von   java.util.Collections.sort zum Sortieren von Objektreferenzen ist ein "Modified"   Mergesort (in dem die Zusammenführung entfällt, wenn das höchste Element in der   niedrige Unterliste ist kleiner als das niedrigste Element in der hohen Unterliste). "Es   ist eine einigermaßen schnelle stabile Sortierung, die O (n log n) garantiert   Leistung und benötigt O (n) zusätzlichen Speicherplatz. Zu seiner Zeit (es wurde geschrieben   im Jahr 1997 von Joshua Bloch), es war eine gute Wahl, aber heute aber wir können   viel besser.

Seit 2003 verwendet Pythons Listensortierung einen Algorithmus namens timsort   (nach Tim Peters, der es geschrieben hat). Es ist stabil, adaptiv, iterativ   Mergesort, der weit weniger als n log (n) Vergleiche erfordert, wenn   läuft auf teilweise sortierten Arrays und bietet Leistung   vergleichbar mit einem traditionellen Mergesort, wenn er auf zufälligen Arrays läuft. Mögen   alle richtigen mergesorts timsort ist stabil und läuft in O (n log n) -Zeit   (schlimmsten Fall). Im schlimmsten Fall benötigt timsort einen temporären Speicher   Platz für n / 2 Objektreferenzen; im besten Fall benötigt es nur ein   kleine konstante Menge an Speicherplatz. Vergleichen Sie dies mit der Strömung   Implementierung, die immer zusätzlichen Platz für n Objekt benötigt   Referenzen, und beats n log n nur auf fast sortierten Listen.

Timsort wird hier ausführlich beschrieben:    http://svn.python.org/projects/python/trunk/Objects/listsort.txt.

Tim Peters ursprüngliche Implementierung ist in C. Joshua Bloch geschrieben   portierte es von C nach Java und beendete das Testen, Benchmarking und Tuning   resultierenden Code ausgiebig. Der resultierende Code ist ein Drop-In   Ersatz für java.util.Arrays.sort. Auf hoch geordneten Daten, dies   Code kann bis zu 25 Mal schneller als die aktuelle Implementierung (on   die HotSpot-Server-VM). Auf zufälligen Daten die Geschwindigkeiten der alten und neuen   Implementierungen sind vergleichbar. Für sehr kurze Listen, die neue   Die Implementierung ist wesentlich schneller als die alten sogar auf Zufall   Daten (weil es unnötiges Kopieren von Daten vermeidet).

Siehe auch Verwendet Java 7 Tim Sort für die Methode Arrays.Sort?.

Es gibt keine einzige "beste" Wahl. Wie bei vielen anderen Dingen geht es um Kompromisse.


156
2018-03-01 09:20