Welche Implementierungen haben Sie betrachtet? Die vom JDK verwendeten primären Sortieralgorithmen sind DualPivotQuicksort
(für primitive Arrays), TimSort
und ComparableTimSort
(für Object
Arrays/Sammlungen) und der unverständliche Wizardy in ArraysParallelSortHelpers
für gleichzeitige Sortierungen.
Alle diese Klassen bieten hochgradig abgestimmte Implementierungen von QuickSort oder MergeSort (oder in dem parallelen Fall "CilkSort", der wie ein Concurrency-freundlicher MergeSort klingt). Diese Algorithmen sind im Allgemeinen alle O (n log (n)) - es ist impossible to do better than O(n log(n)) ohne zusätzliche Einschränkungen für Ihre Eingaben.
Zur Frage, ob diese Algorithmen im Allgemeinen verbringen O (n) Zeit Kopieren Werte Hin- und Herschalten zwischen temporären Speicher, es ist sehr viel ein Fall-zu-Fall-Frage. Wo es möglich ist, werden diese Implementierungen sicherlich versuchen, die Verwendung von O (n) extra Speicher und Zeit für lineares Kopieren zu vermeiden, aber oft ist diese Arbeit nicht wirklich der Flaschenhals. Zum Beispiel verwendet CilkSort ein sekundäres "Workspace Array", um Werte in aufeinanderfolgenden Stufen hin und her zu kopieren, was das Erzwingen von Invarianten erleichtert, da die "vorherige" Stufe immer in einem zuverlässigen Zustand ist. Trotzdem versuchen die Implementierungen unnötige Array-Kopien zu vermeiden, wann immer dies möglich ist.
Auf der öffentlichen API-Ebene werden wir feststellen, dass Collections.sort()
ruft .toArray()
, sortiert das Array, und kopiert dann die Werte zurück in das Original List
. Dies ist in ähnlicher Weise nur eine praktische Optimierung - es schneller ist, ein Array zu sortieren und zu tun, zwei lineare Kopien als mit allen Methodenaufrufen zu behandeln (und möglicherweise ineffizient List
Implementierungen, wie LinkedList
) die List
an Ort und Stelle zu ändern.
Ja. O (2n logn) ist immer noch O (n logn). – Thilo
Plus, Array-Division passiert in-Place. nicht neues Array an sich. –
Ich versuche eine In-Place-Array-Division zu implementieren, aber es scheint irgendwie chaotisch. Sie müssen den Anfangs- und Endindex Ihres ursprünglichen Arrays verfolgen, oder? Es scheint nicht zu schwierig zu implementieren, aber es scheint definitiv, als gäbe es mehr Orte für Fehler als wenn Sie nur ein neues linkes und ein neues rechtes Array erstellen. – Kevin