Die Arrays.sortMethode von Java 6 verwendet Quicksort für Arrays von Grundelementen und Merge Sort für Arrays von Objekten. Ich glaube, dass Quicksort die meiste Zeit schneller als das Zusammenführen ist und weniger Speicher kostet. Meine Experimente unterstützen dies, obwohl beide Algorithmen O (n log (n)) sind. Warum werden unterschiedliche Algorithmen für unterschiedliche Typen verwendet?
121
Integers oder etwas haben?Antworten:
Der wahrscheinlichste Grund: Quicksort ist nicht stabil , dh gleiche Einträge können ihre relative Position während der Sortierung ändern. Dies bedeutet unter anderem, dass ein bereits sortiertes Array möglicherweise nicht unverändert bleibt.
Da primitive Typen keine Identität haben (es gibt keine Möglichkeit, zwei Ints mit demselben Wert zu unterscheiden), spielt dies für sie keine Rolle. Bei Referenztypen kann dies jedoch bei einigen Anwendungen zu Problemen führen. Daher wird für diese eine stabile Zusammenführungssortierung verwendet.
OTOH, ein Grund, die (garantierte n * log (n)) stabile Zusammenführungssortierung für primitive Typen nicht zu verwenden, könnte sein, dass ein Klon des Arrays erstellt werden muss. Bei Referenztypen, bei denen die referenzierten Objekte normalerweise viel mehr Speicherplatz beanspruchen als das Referenzarray, spielt dies im Allgemeinen keine Rolle. Bei primitiven Typen verdoppelt das vollständige Klonen des Arrays die Speichernutzung.
quelle
Gemäß den in dieser Antwort zitierten Java 7-API-Dokumenten wird
Arrays#Sort()für Objektarrays jetzt TimSort verwendet , eine Mischung aus MergeSort und InsertionSort. Auf der anderen Seite wirdArrays#sort()für primitive Arrays jetzt Dual-Pivot QuickSort verwendet . Diese Änderungen wurden ab Java SE 7 implementiert.quelle
Ein Grund, den ich mir vorstellen kann, ist, dass Quicksort eine Worst-Case-Zeitkomplexität von O ( n ^ 2 ) aufweist, während Mergesort die Worst-Case-Zeit von O ( n log n ) beibehält . Für Objektarrays besteht eine angemessene Erwartung, dass es mehrere doppelte Objektreferenzen geben wird. Dies ist ein Fall, in dem Quicksort am schlechtesten abschneidet.
Es gibt einen anständigen visuellen Vergleich verschiedener Algorithmen . Achten Sie besonders auf das Diagramm ganz rechts für verschiedene Algorithmen.
quelle
Ich nahm an einem Coursera-Kurs über Algorithmen teil und erwähnte in einer der Vorlesungen Professor Bob Sedgewick die Bewertung für die Sortierung von Java-Systemen:
quelle
java.util.Arrays Verwendungen QuickSort für primitive Typen wie int und mergesort für Objekte , die implementieren Comparable oder verwenden Vergleicher . Die Idee, zwei verschiedene Methoden zu verwenden, besteht darin, dass, wenn ein Programmierer Objekte verwendet, möglicherweise Platz keine kritisch wichtige Überlegung ist und der zusätzliche Speicherplatz, der von Mergesort verwendet wird, möglicherweise kein Problem darstellt. Wenn der Programmierer primitive Typen verwendet, ist möglicherweise die Leistung das Wichtigste die Quicksort .
Zum Beispiel: Dies ist das Beispiel, wenn es um die Sortierstabilität geht.
Aus diesem Grund sind stabile Sortierungen für Objekttypen sinnvoll, insbesondere für veränderbare Objekttypen und Objekttypen mit mehr Daten als nur dem Sortierschlüssel, und Mergesort ist eine solche Sortierung. Für primitive Typen ist Stabilität jedoch nicht nur irrelevant. Es ist bedeutungslos.
Quelle: INFO
quelle
Javas
Arrays.sortMethode verwendet Quicksort, Einfügesortierung und Mergesort. Im OpenJDK-Code ist sogar ein QuickSort mit einem und zwei Pivots implementiert. Der schnellste Sortieralgorithmus hängt von den Umständen ab und die Gewinner sind: Einfügesortierung für kleine Arrays (47 derzeit ausgewählt), Zusammenführungssortierung für meist sortierte Arrays und Quicksortierung für die verbleibenden Arrays, sodass Javas Array.sort () versucht, den besten Algorithmus auszuwählen bewerben sich nach diesen Kriterien.quelle