Was bedeutet schnelle Sortierung?

Schnellsortierung ist eine Verbesserung der Blasensortierung. Ihr Implementierungsprinzip besteht darin, die unsortierten Elemente basierend auf einem „Pivot“ als Benchmark aufzuteilen. Die Datensätze in einer der Untersequenzen sind größer als das Hauptelement .-Element und die andere Teilsequenz ist kleiner als das Pivot-Element, und dann werden die beiden Teilsequenzen mit einer ähnlichen Methode rekursiv sortiert.

Schnellsortierung

Unterteilt unsortierte Elemente in Gruppen basierend auf einem „Pivot“ als Grundlage Zwei Teilsequenzen, von denen eine Datensätze größer als der Pivot hat, während die andere Teilsequenz kleiner als der Pivot ist, dann sortieren Sie die beiden Teilsequenzen rekursiv auf ähnliche Weise

Zeitkomplexität: O(Nlog2N)

Einleitung:

Quicksort ist eine Verbesserung der Blasensortierung.

Schnellsortierung wurde 1960 von C. A. R. Hoare vorgeschlagen. Seine Grundidee besteht darin, die zu sortierenden Daten durch eine Sortierung in zwei unabhängige Teile zu unterteilen. Alle Daten in einem Teil sind kleiner als alle Daten im anderen Teil und dann wird diese Methode verwendet, um die beiden Teile der Daten schnell zu trennen Beim Sortieren kann der gesamte Sortiervorgang rekursiv durchgeführt werden, sodass die gesamten Daten zu einer geordneten Sequenz werden.

Das obige ist der detaillierte Inhalt vonWas bedeutet schnelle Sortierung?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!