Schnelle Sortierung mit Python

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)

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)

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!