Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Merge sort in 3 minutes
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 12 Zeilen
- Heute werden wir Mergesort ein paar kurze Punkte lernen, dann kommen wir zu dem Beispiel Mergesort wird normalerweise rekursiv durchgeführt, wenn Sie an Mergesort denken, wie bei
- anderen rekursiven Algorithmen Teilen Sie unser Problem in kleinere Probleme auf, um es zu lösen. Fangen wir an. Wir
- haben das folgende Array und wir möchten, dass es sortiert wird. Wir werden das Array kontinuierlich in zwei
- Hälften teilen, bis wir mit den einzelnen Elementen übrig bleiben Unsere Arrays sind jetzt in einzelne Elemente unterteilt, eine Notiz, bevor wir mit dem Sortieren beginnen. Wenn
- Sie dies im Code implementieren, haben wir diese Schritte aufgrund der Rekursion in einer anderen Reihenfolge ausgeführt, aber ich denke, diese benutzerfreundliche Reihenfolge bietet mehr Klarheit und Lernen. Lassen Sie uns fortfahren
- to sort untersucht die einzelnen Elemente, vergleicht ihre Werte und führt sie zu temporären Arrays zusammen .
- Die temporären Strahlen sind sortiert, aber es bleibt noch etwas zu tun r kleinere Arrays in ein größeres einfügen Elemente in der richtigen Reihenfolge einfügen
- Sie noch einmal zusammenführen und wir haben unser sortiertes Array
- Sie und das war's, unser Array ist jetzt sortiert hier ist der Pseudocode
- für Merge-Sort auf der linken Seite Sie haben den rekursiven Teil, der halbiert Die Arrays auf der rechten Seite sind die Zusammenführungsfunktion, die die Arrays kombiniert
- . Mergesort hat eine Worst-Case-Zeitkomplexität von Big O von n-mal log. Die einfachste Art, darüber nachzudenken , besteht darin, mit dem Zusammenführungsschritt zu beginnen und die While-Schleife zu betrachten, die wir sehen muss n Elemente besuchen das Log
- n kommt von der maximalen Höhe eines von uns erstellten binären Baums, der in der Größenordnung von log N liegt