Wie schreibe ich den Hill-Sortieralgorithmus in Python?

Wie schreibe ich den Hill-Sortieralgorithmus in Python?

Shell Sort ist ein verbesserter Einfüge-Sortieralgorithmus, der Elemente durch den Vergleich von Elementen in einem bestimmten Intervall verschiebt und dadurch die Anzahl der Verschiebungen reduziert. Die Kernidee der Hill-Sortierung besteht darin, die zu sortierenden Elemente nach einem bestimmten Intervall zu gruppieren und dann für jede Gruppe eine Einfügungssortierung durchzuführen, das Intervall kontinuierlich zu reduzieren, bis es 1 ist, und schließlich eine vollständige Einfügungssortierung durchzuführen.

Im Folgenden stellen wir detailliert vor, wie der Hill-Sortieralgorithmus in Python geschrieben wird.

Zuerst müssen wir eine Funktion schreiben, um die Einfügungssortierung zu implementieren. Die Kernidee der Einfügesortierung besteht darin, das aktuelle Element in die bereits sortierte vorherige Sequenz einzufügen.

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

Als nächstes schreiben wir eine Hill-Sortierfunktion, die eine zu sortierende Liste als Parameter empfängt.

def shell_sort(arr):
    n = len(arr)
    gap = n // 2  # 初始间隔设置为列表长度的一半
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap = gap // 2  # 缩小间隔

Abschließend schreiben wir eine Testfunktion, um die Richtigkeit der Hill-Sortierung zu überprüfen.

def test_shell_sort():
    arr = [12, 34, 55, 23, 8, 17, 45, 91]
    shell_sort(arr)
    assert arr == [8, 12, 17, 23, 34, 45, 55, 91]
    print("希尔排序测试通过！")

if __name__ == "__main__":
    test_shell_sort()

Wenn nach dem Ausführen der Testfunktion kein Fehler gemeldet wird und die Meldung „Hill-Sort-Test bestanden!“ ausgegeben wird, bedeutet dies, dass die Implementierung der Hill-Sortierung korrekt ist.

Die zeitliche Komplexität der Hill-Sortierung hängt mit der ausgewählten Intervallsequenz zusammen. Die beste Intervallsequenz wurde noch nicht gefunden. Die durchschnittliche Zeitkomplexität der Hill-Sortierung beträgt etwa O(n^1,3) und die Zeitkomplexität im ungünstigsten Fall beträgt etwa O(n^2).

Hill-Sortierung ist ein effizienter Sortieralgorithmus. Im Vergleich zur Einfügungssortierung kann er die Elemente der Einfügungssortierung zu Beginn teilweise ordnen, wodurch nachfolgende Vergleichs- und Verschiebungsvorgänge reduziert und die Sortiereffizienz verbessert werden. Wenn Sie eine Liste schnell sortieren möchten, versuchen Sie es mit dem Hill-Sortieralgorithmus.

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