Lernen und implementieren Sie den Auswahlsortierungsalgorithmus in Python

Verstehen Sie das Prinzip und die Implementierung der Auswahlsortierung in Python. Die Grundidee der Auswahlsortierung besteht darin, das Array jedes Mal zu durchlaufen und das kleinste (oder größte) Element im unsortierten Teil auszuwählen , tauschen Sie seine Position mit dem ersten Element des unsortierten Teils und wählen Sie dann weiterhin das kleinste (oder größte) Element aus dem unsortierten Teil aus usw., bis das gesamte Array sortiert ist. Die zeitliche Komplexität der Auswahlsortierung beträgt O(n^2) und es handelt sich um einen instabilen Sortieralgorithmus.

Im Folgenden werden spezifische Codebeispiele verwendet, um den Implementierungsprozess der Auswahlsortierung zu veranschaulichen.

def selection_sort(arr):
    n = len(arr)
    for i in range(n-1):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

Das Obige ist der Implementierungscode des Auswahlsortierungsalgorithmus. Als nächstes erklären wir Schritt für Schritt das Prinzip und den Prozess dieses Codes.

Zuerst definieren wir eine Funktion „selection_sort“, die als Parameter ein zu sortierendes Array arr empfängt.

Im Funktionskörper erhalten wir zunächst die Länge n des Arrays. Dies erfolgt n-1 Mal, da bei jeder Iteration das kleinste Element an der richtigen Position platziert wird, sodass das letzte Element nicht sortiert werden muss.

Dann verwenden wir zwei verschachtelte for-Schleifen, um den Auswahlsortierungsprozess durchzuführen. Die äußere Schleife geht von 0 bis n-1 und stellt die Startposition i des zu sortierenden Teils dar.

Die innere Schleife reicht von i+1 bis n und repräsentiert das Element j im zu sortierenden Teil. Wir vergleichen j mit dem Element an der Startposition i. Wenn j kleiner als das Element an der Startposition i ist, wird min_idx auf j aktualisiert, was anzeigt, dass j der Index des kleinsten bisher gefundenen Elements ist.

Wenn die innere Schleife endet, tauschen wir die Position des kleinsten gefundenen Elements mit dem Element an der Startposition i aus, sodass die aktuelle Iteration ein kleinstes Element an der richtigen Position platziert.

Mit n-1 Iterationen können wir sicherstellen, dass das gesamte Array in aufsteigender Reihenfolge sortiert wird.

Als nächstes können wir den folgenden Code verwenden, um die Wirkung der Auswahlsortierung zu testen:

arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("排序后的数组：")
for i in range(len(arr)):
    print(arr[i], end=" ")

Das Ausgabeergebnis ist: 11 12 22 25 64, was bedeutet, dass das Array in aufsteigender Reihenfolge sortiert wurde.

Bei der tatsächlichen Verwendung ist die Auswahlsortierung weniger effizient, daher bevorzugen wir die Verwendung anderer effizienterer Sortieralgorithmen, wie z. B. Schnellsortierung oder Zusammenführungssortierung. Die Auswahlsortierung ist jedoch ein einfacher und leicht verständlicher Sortieralgorithmus, der für Anfänger hilfreich ist, um die Grundprinzipien und Ideen von Sortieralgorithmen zu verstehen.

Zusammenfassend besteht die Auswahlsortierung darin, jedes Mal das kleinste (oder größte) Element aus dem unsortierten Teil auszuwählen, es am Ende des sortierten Teils einzufügen und durch mehrere Iterationen schließlich den Zweck zu erreichen, das gesamte Array zu ordnen. Die Beherrschung des Prinzips und der Implementierung der Auswahlsortierung ist für ein tiefgreifendes Verständnis der Sortieralgorithmen und die Verbesserung der Programmierfähigkeiten von großer Bedeutung.

Das obige ist der detaillierte Inhalt vonLernen und implementieren Sie den Auswahlsortierungsalgorithmus in Python. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!