Heute starten [EINFÜHRUNG IN ALGORITHMEN](https://www.amazon.co.jp/Introduction-Algorithms-Thomas-H-Cormen/dp/8120340078/ref=sr_1_2?__mk_ja_JP=Katakana & keywords = Einführung + in + Algorithmus & qid = 15810 Seit ich mit dem Lesen von -2) angefangen habe, gibt es viele einfache Inhalte, aber ich werde den Algorithmus zusammenfassen.

Sortierung einfügen

Das Sortieren eines Arrays mit 10 Elementen nach Einfügesortierung ähnelt dem folgenden Beispiel.

Es liegen 10 Spielkarten auf dem Tisch und die Anzahl der Karten auf Ihrer Hand beträgt zu Beginn 0. Ich ziehe nacheinander Karten vom Tisch und füge sie meiner Hand hinzu, aber ich halte meine Hand immer in aufsteigender Reihenfolge sortiert. Sie möchten Ihre Hand sauber halten, wie eine Karte mit einer kleinen Nummer links und eine Karte mit einer großen Nummer rechts. Der Punkt dieses Prozesses ist, dass ** Karten in drei Typen ** klassifiziert werden können.

Bereits sortierte Karten in der Hand
Die Karte, die Sie aus der Tabelle hinzufügen möchten
Karten noch auf dem Tisch

Die Sortierung einfügen beachtet dies ebenfalls.

Der Teil des Arrays, der bereits in aufsteigender Reihenfolge sortiert wurde
Das Element, das Sie im Array betrachten
Der Teil des Arrays, der noch nicht in aufsteigender Reihenfolge sortiert wurde

Zum Beispiel

Index	0	1	2	3	4	5	6	7	8	9
Wert	5	3	8	1	2	4	7	6	9	0

Angenommen, Sie haben ein Array mit 10 Elementen. Stellen Sie sich vor, alle Karten liegen noch auf dem Tisch. Angenommen, Sie ziehen jeweils eine Karte und ziehen nur die fünfte. Dies entspricht der Tatsache, dass das Array auf Index 0-3 sortiert wurde und sich nun auf Index 4-2 konzentriert.

Index	0	1	2	3	4	5	6	7	8	9
Wert	1	3	5	8	2	4	7	6	9	0

Lassen Sie uns nun die Position finden, an der diese 2 eingefügt werden soll.

――Vergleichen Sie 2 und 8, 8 ist größer, ersetzen Sie also die Positionen 2 und 8. ――Vergleicht man 2 und 5, ist 5 größer, also tauschen Sie die Positionen 2 und 5 aus. ――Vergleicht man 2 und 3, ist 3 größer, ersetzen Sie also die Positionen 2 und 3. ――Vergleich von 2 und 1 ist 2 größer und endet hier.

Machen Sie dasselbe für die 6. bis 10. Karte, um ein sortiertes Array zu erhalten. Dies ist das Sortierverfahren für Einfügungen.

def insertion_sort(a) -> None:
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while key < a[j] and j >= 0:
            a[j+1] = a[j] 
            j -= 1
        a[j+1] = key

a = [1, 3, 5, 8, 2, 4, 7, 6, 9, 0]
insertion_sort(a)
print(a)

Ausgabe

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Der Text, den ich zu Beginn eingeführt habe, erklärt verschiedene Dinge über einen Algorithmus, z. B. warum Sie Seiten mit Einfügesortierung so stark unterteilen können, dass ich einen weiteren Artikel schreiben werde, wenn es etwas zu lesen und zu ergänzen gibt. ..

[PYTHON] Sortierung einfügen

Sortierung einfügen