Einführung in die Methode zum Zusammenführen von Sortierungen mithilfe der Python-Programmierung

Dieser Artikel stellt hauptsächlich den spezifischen Code der PythonProgrammierung vor, um die Zusammenführungssortierung zu erreichen. Interessierte Freunde können sich darauf beziehen.

Aus diesem Grund Als ich letzte Woche eine Frage zu Leetcode stellte (Median of Two

Sorted Arrays), wollte ich mir die Implementierung von Merge Sort genauer ansehen.

Lassen Sie mich zunächst die Sortieridee erläutern:

Zuerst verwendet die Zusammenführungssortierung die Dichotomiemethode. Letztendlich besteht die Idee darin, zu teilen und zu erobern. Holen Sie sich ein langes

Array, teilen Sie es kontinuierlich in den linken und rechten Teil auf und teilen Sie es dann rekursiv auf. Führen Sie sie dann zu zwei geordneten Arrays zusammen. Auf diese Weise ist es möglicherweise schwer zu verstehen, daher gebe ich Ihnen ein Bild, das ich gezeichnet habe.

Dies zeigt den ersten Schritt der Zusammenführungssortierung. Das Array wird rekursiv nach Mitte

dle aufgeteilt und schließlich in kleinste Details unterteilt Sortiert zwei sortierte Arrays mit der gleichen Methode wie beim Sortieren.

Die Methode zum Sortieren zweier geordneter

Arrays ist sehr einfach. Vergleichen Sie gleichzeitig die ersten Positionen der beiden Arrays, fügen Sie das kleinere in ein leeres Array ein und fügen Sie es dann ein Der Zeiger an der Position des leeren Arrays wird um eins zurückbewegt und dann weiterhin mit der vorherigen Position des anderen Arrays verglichen, und so weiter. Wenn das letzte Array zuerst vom Stapel entfernt wird, werden alle Elemente im anderen Array an das neue Array angehängt.

Da die Zeitkomplexität der rekursiven Aufteilung jedoch logN beträgt, beträgt die Komplexität der Methode zum Sortieren zweier geordneter Arrays N. Die Zeitkomplexität dieses Algorithmus beträgt N*logN, also NlogN.

Anhand dieser Analysewelle können wir ein

Verhalten des obigen Bildes betrachten.

Wenn der Teil ganz links in kleinste Details unterteilt ist, kann er nicht mehr in einen linken und einen rechten Teil unterteilt und dann zusammengeführt werden.

Die erste Kombination vervollständigt die Zusammenführung von [4, 7]

Die zweite Kombination vervollständigt die Zusammenführung von [4, 7, 8]

Die dritte Kombination vervollständigt[ The Zusammenführung von 3, 5]

Die vierte Kombination ist abgeschlossen. Die Zusammenführung von [3, 5, 9]

Die fünfte Kombination ist abgeschlossen [3, 4, 5, 7, 8, 9 ] Die Zusammenführung beendet die Sortierung.

Geben Sie den Python-Code unten ein

Das obige ist der detaillierte Inhalt vonEinführung in die Methode zum Zusammenführen von Sortierungen mithilfe der Python-Programmierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!