Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Quick sort in 4 minutes
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 18 Zeilen
- Heute lernen wir Quicksort wie Merge Sort Quicksort ist ein rekursiver Algorithmus, aber wenn Sie an Quicksort denken, denken Sie bitte an das Wort Pivot. Ein Pivot ist einfach eines der
- Elemente im Array, das die folgenden drei Bedingungen nach we bedeutet Wenn Sie es zuerst sortiert haben, befindet sich der Drehpunkt an der richtigen Position im endgültigen sortierten Array. Dies bedeutet, dass alle Elemente links kleiner
- und alle Elemente rechts größer sind. Sehen wir uns ein Beispiel an, in dem wir gebeten werden, das folgende Array zu sortieren Pivot Ich werde später erklären, wie das am besten geht, aber jetzt
- wählen wir einfach drei aus. Zuerst verschieben wir den Pivot an das Ende des Arrays, um ihn aus dem Weg zu räumen. Als nächstes suchen wir nach zwei Elementen item von links Das ist das erste Element
- , das von links beginnt und größer ist als unser Pivot. Das zweite Element von rechts , das das erste Element ist, das von rechts
- beginnt und kleiner ist als unser Pivot rechts sehen wir, dass man es ist em von rechts
- Lassen Sie uns das Element von links mit dem Element von rechts tauschen. Wir wiederholen den Vorgang, diesmal ist fünf das Element von links und null ist
- erneut das Element von rechts. Wir tauschen die beiden noch einmal aus. Dieses Mal sehen wir, dass das Element von
- links einen größeren Index hat als Element von rechts, damit wir wissen, dass wir fertig sind. Wir tauschen Element von links mit unserem Drehpunkt
- 3. Unser Drehpunkt befindet sich jetzt an der richtigen Stelle, um dies zu beweisen. Lassen Sie uns unsere drei Bedingungen überprüfen, da Sie sehen können, dass alle Elemente auf der linken Seite kleiner sind und alle Elemente zu die rechten
- sind größer wir sagten Quicksort ist rekursiv Lassen Sie uns den Prozess noch einmal mit der größeren Partition durchgehen, die wir gerade erstellt haben Wir wählen 7 als Drehpunkt und verschieben sie ans Ende
- Ich lasse Sie jetzt ohne Voiceover zuschauen, was Sie
- jetzt haben drei und sieben an ihren richtigen Positionen Ich denke, Sie verstehen das Konzept, also überlassen wir den Rest der Rekursion .
- Eine wichtige Frage ist, wie wir den Drehpunkt auswählen. Dies macht einen großen Unterschied in der Leistung des Algorithmus, da wir einen Drehpunkt auswählen möchten das teilt das Array i
- In der Hälfte oder so nah wie möglich, um die Arbeit auszugleichen, heißt eine beliebte Methode Dreiertreffen. Bei dieser Methode sehen wir uns die ersten mittleren und letzten Elemente des Arrays an
- . Wir sortieren sie richtig und wählen das mittlere Element als unseren Dreh- und Angelpunkt Vermuten Sie , dass die Mitte dieser drei Elemente nahe am Median des
- gesamten Arrays liegen könnte, und wie Sie sehen können, ist es nicht zu weit davon entfernt. Hier ist der Pseudocode für Quicksort Wenn
- ein Pivot richtig gewählt ist, kann gezeigt werden, dass es sich um einen durchschnittlichen Fall von Big O und Log N handelt. Vielen Dank für das Ansehen. Bitte liken und abonnieren, wenn Ihnen das Video gefallen hat