Wie schreibe ich einen Einfügungssortierungsalgorithmus in Python?

Wie schreibe ich einen Einfügungssortierungsalgorithmus in Python?

Einfügesortierung ist ein einfacher und intuitiver Sortieralgorithmus. Seine Idee besteht darin, das zu sortierende Array in einen geordneten Teil und einen ungeordneten Teil zu unterteilen. Jedes Mal wird ein Element aus dem ungeordneten Teil ausgewählt und an der richtigen Position eingefügt bestelltes Teil. Die Implementierung des Einfügungssortierungsalgorithmus erfolgt normalerweise durch mehrmaliges Vergleichen und Austauschen von Elementen mit einer zeitlichen Komplexität von O(n^2).

Werfen wir einen Blick darauf, wie der Einfügesortierungsalgorithmus in der Python-Sprache geschrieben wird, sowie auf spezifische Codebeispiele.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]              # 当前待插入元素
        j = i - 1                 # 有序部分的最后一个元素索引

        # 将比key大的元素都向后移动一位
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key           # 将key插入正确位置

    return arr

Das Obige ist der spezifische Implementierungscode des Einfügungssortierungsalgorithmus. In der Hauptfunktion müssen wir ein zu sortierendes Array arr übergeben und das sortierte Ergebnis zurückgeben.

In der Hauptschleife des Algorithmus beginnen wir mit dem zweiten Element und verwenden es als Schlüssel des einzufügenden Elements. Anschließend vergleichen wir den Schlüssel mit dem letzten Element des sortierten Teils und verschieben das Element, das größer als der Schlüssel ist, eine Position nach hinten, bis wir die richtige Position des Schlüssels gefunden haben. Zum Schluss stecken wir den Schlüssel an die richtige Stelle.

Als nächstes können wir diesen Einfügungssortierungsalgorithmus testen.

arr = [9, 5, 1, 6, 8, 2]
sorted_arr = insertion_sort(arr)
print(sorted_arr)

Das Ausgabeergebnis ist:

[1, 2, 5, 6, 8, 9]

Sie können sehen, dass wir durch den Einfügungssortierungsalgorithmus das Eingabearray erfolgreich in aufsteigender Reihenfolge angeordnet haben.

Zusammenfassend lässt sich sagen, dass das Schreiben des Einfügungssortierungsalgorithmus in Python nicht kompliziert ist. Wir müssen nur die Grundidee der Einfügungssortierung verstehen und dann den entsprechenden Code basierend auf der Idee implementieren. Um den Code robuster und vielseitiger zu machen, können wir natürlich auch Randfälle wie leere Arrays oder Arrays mit nur einem Element verarbeiten.

Ich hoffe, dieser Artikel kann Ihnen helfen, den Einfügungssortierungsalgorithmus zu verstehen und zu beherrschen!

Das obige ist der detaillierte Inhalt vonWie schreibe ich einen Einfügungssortierungsalgorithmus in Python?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!