Schnelle Sortierung mit Python

PHPz
Freigeben: 2023-06-10 16:36:21
Original
5569 Leute haben es durchsucht

Schnellsortierung ist ein häufig verwendeter Sortieralgorithmus mit einer Zeitkomplexität von O(nlogn). In praktischen Anwendungen ist die schnelle Sortierung normalerweise viel schneller als andere Sortieralgorithmen. Python bietet viele integrierte Sortierfunktionen, es ist jedoch dennoch wichtig, Quicksort zu verstehen und zu implementieren. In diesem Artikel implementieren wir den Schnellsortierungsalgorithmus über Python.

Schnellsortierung funktioniert durch die Auswahl eines Pivot-Werts (Pivot), das anschließende Platzieren aller Elemente in der Liste, die kleiner als der Pivot-Wert sind, in einer Unterliste und das Platzieren aller Elemente, die größer als der Pivot-Wert sind, in einer anderen Unterliste. Die beiden Teillisten werden dann schnell rekursiv sortiert. Schließlich werden alle Unterlisten rekursiv sortiert und dann zu einer einzigen sortierten Liste zusammengeführt.

Hier ist der Code zum Implementieren der Schnellsortierung in Python:

def quick_sort(arr): if len(arr) < 2: return arr else: pivot = arr[0] less = [i for i in arr[1:] if i <= pivot] greater = [i for i in arr[1:] if i > pivot] return quick_sort(less) + [pivot] + quick_sort(greater)
Nach dem Login kopieren

Im obigen Code überprüfen wir zunächst die Länge der Liste. Wenn die Listenlänge kleiner als 2 ist, geben wir die ursprüngliche Liste zurück. Andernfalls wählen wir das erste Element der Liste als Pivotwert aus. Anschließend verwenden wir Listenverständnisse, um Elemente, die kleiner oder gleich dem Pivot-Wert sind, in eine Liste einzufügen und Elemente, die größer als der Pivot-Wert sind, in eine andere Liste. Als nächstes sortieren wir die kleineren und größeren Listen rekursiv und verketten die sortierten Listen miteinander, wobei der Pivot-Wert in der Mitte der verketteten Listen platziert wird.

Dieser Algorithmus muss eine geeignete Referenznummer auswählen. Wenn die gewählte Basiszahl zufällig der größte (oder kleinste) Wert in der Liste ist, wird die Größe der rekursiv sortierten Unterliste nur um 1 reduziert. In diesem Fall kann die Zeitkomplexität des Quicksort-Algorithmus auf O(n2) degenerieren. Um dies zu vermeiden, können wir die Methode der zufälligen Auswahl des Basiswerts verwenden. Diese Methode garantiert die durchschnittliche Größe der rekursiv sortierten Unterlisten in Fällen, in denen der Basiswert nicht der größte (oder kleinste) Wert in der Liste ist.

Hier ist der Python-Code für die zufällige Auswahl des Benchmark-Werts:

import random def quick_sort(arr): if len(arr) < 2: return arr else: pivot_index = random.randint(0, len(arr) - 1) pivot = arr[pivot_index] less = [i for i in arr[:pivot_index] + arr[pivot_index + 1:] if i <= pivot] greater = [i for i in arr[:pivot_index] + arr[pivot_index + 1:] if i > pivot] return quick_sort(less) + [pivot] + quick_sort(greater)
Nach dem Login kopieren

Im obigen Code wählen wir zunächst zufällig einen Benchmark-Wert mit der Funktion random.randint() aus. Anschließend fügen wir die Elemente, die kleiner oder gleich dem Basiswert sind, in eine Liste ein und die Elemente, die größer als der Basiswert sind, in eine andere Liste, die der vorherigen Implementierung ähnelt.

Zusammenfassend haben wir den Schnellsortierungsalgorithmus über Python implementiert und die Methode der zufälligen Auswahl des Benchmark-Werts verwendet, um das Ungleichgewicht in der Größe der rekursiv sortierten Unterliste zu vermeiden. Dieser Algorithmus basiert auf der Idee von „Divide and Conquer“, wodurch die Liste schnell mit einer durchschnittlichen Zeitkomplexität von O(nlogn) sortiert werden kann.

Das obige ist der detaillierte Inhalt vonSchnelle Sortierung mit Python. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Verwandte Etiketten:
Quelle:php.cn
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage
Über uns Haftungsausschluss Sitemap
Chinesische PHP-Website:Online-PHP-Schulung für das Gemeinwohl,Helfen Sie PHP-Lernenden, sich schnell weiterzuentwickeln!