So implementieren Sie die Zusammenführungssortierung mit Python

Merge Sort ist ein klassischer Sortieralgorithmus. Seine Kernidee besteht darin, das zu sortierende Array in mehrere Unterarrays aufzuteilen, diese Unterarrays zu sortieren und schließlich die sortierten Unterarrays zu einem geordneten Array zusammenzuführen. Merge Sort ist ein relativ effizienter Sortieralgorithmus mit einer Zeitkomplexität von O(nlogn).

In diesem Artikel erklären wir, wie man die Zusammenführungssortierung in Python implementiert.

1. Die Idee, die Zusammenführungssortierung zu implementieren

Die Idee, die Zusammenführungssortierung zu implementieren, besteht aus zwei Teilen, nämlich Teilen und Erobern und Zusammenführen. Die spezifischen Implementierungsschritte sind wie folgt:

1) Teilen Sie das zu sortierende Array weiterhin in zwei Teile und sortieren Sie den linken und rechten Teil rekursiv.

2) Führen Sie die sortierten linken und rechten Teile zu einem geordneten Array zusammen.

2. Verwenden Sie Python, um „Teile und herrsche“ zu implementieren. „Teile und herrsche“ ist die Kernidee der Zusammenführungssortierung. Wir müssen zuerst den Teil „Teile und herrsche“ implementieren.

Der Code lautet wie folgt:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left_arr = merge_sort(arr[:mid])
    right_arr = merge_sort(arr[mid:])
    return merge(left_arr, right_arr)

In dieser Funktion ermitteln wir zunächst, ob die Array-Länge kleiner oder gleich 1 ist, und geben dann das Array direkt zurück. Andernfalls müssen wir das Array in zwei Teile teilen, den linken bzw. rechten Teil rekursiv sortieren und schließlich den sortierten linken und rechten Teil zusammenführen.

2.1 Fusion umsetzen

Auf der Grundlage von Teilen und Erobern müssen wir den Fusionsteil implementieren.

Der Code lautet wie folgt:

def merge(left_arr, right_arr):
    i, j = 0, 0
    result = []
    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] < right_arr[j]:
            result.append(left_arr[i])
            i += 1
        else:
            result.append(right_arr[j])
            j += 1
    result += left_arr[i:]
    result += right_arr[j:]
    return result

In dieser Funktion initialisieren wir zunächst die Zeiger i und j, die auf die zu vergleichenden Elemente im linken bzw. rechten Teil zeigen. Dann vergleichen wir kontinuierlich das linke und das rechte Element, fügen das kleinere Element zur Ergebnisliste hinzu und bewegen den Zeiger nach rechts. Schließlich fügen wir der resultierenden Liste auch alle verbleibenden Elemente hinzu, sodass wir am Ende ein sortiertes Array erhalten.

Vollständiger Code

3. Durch die Kombination der Teile „Divide and Conquer“ und „Merge“ lautet der vollständige Code wie folgt:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left_arr = merge_sort(arr[:mid])
    right_arr = merge_sort(arr[mid:])
    return merge(left_arr, right_arr)

def merge(left_arr, right_arr):
    i, j = 0, 0
    result = []
    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] < right_arr[j]:
            result.append(left_arr[i])
            i += 1
        else:
            result.append(right_arr[j])
            j += 1
    result += left_arr[i:]
    result += right_arr[j:]
    return result

Testen

4. Um zu überprüfen, ob unser Zusammenführungssortiercode korrekt ist, müssen wir einen Test durchführen .

Der Code lautet wie folgt:

arr = [5, 3, 8, 6, 4, 7, 2, 1]
print(merge_sort(arr))

Das Ausgabeergebnis ist:

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

Die Testergebnisse zeigen, dass unser Zusammenführungssortiercode korrekt ist.

Das obige ist der detaillierte Inhalt vonSo implementieren Sie die Zusammenführungssortierung mit Python. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!