Wie implementiert man einen Merge-Sort-Algorithmus mit Python?

Wie implementiert man den Merge-Sort-Algorithmus mit Python?

Merge Sort ist ein gängiger Sortieralgorithmus, der das Prinzip „Teile und herrsche“ nutzt, um ein großes Problem in mehrere zu lösende kleine Probleme aufzuteilen und dann die Lösungen zu den kleinen Problemen zusammenzuführen. Die zeitliche Komplexität der Zusammenführungssortierung beträgt O(nlogn) und eignet sich für Datensätze unterschiedlicher Größe.

Im Folgenden stellen wir detailliert vor, wie Python zum Implementieren des Merge-Sort-Algorithmus verwendet wird, und geben spezifische Codebeispiele.

Die Grundidee der Zusammenführungssortierung besteht darin, das zu sortierende Array in zwei Unterarrays aufzuteilen, dann jedes Unterarray separat zu sortieren und schließlich die sortierten Unterarrays zusammenzuführen. Die spezifischen Schritte sind wie folgt:

1. Teilen Sie das zu sortierende Array kontinuierlich in zwei Unterarrays auf, bis jedes Unterarray nur noch ein Element enthält. Dies kann durch Rekursion erreicht werden.
2. Sortieren Sie jedes Unterarray. Sie können Rekursion oder Iteration verwenden.
3. Kombinieren Sie die sortierten Unterarrays, um das endgültige geordnete Array zu bilden.

Das Folgende ist ein Beispielcode zum Implementieren der Zusammenführungssortierung in Python:

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

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

# 测试
arr = [5, 2, 8, 1, 9, 3]
sorted_arr = merge_sort(arr)
print(sorted_arr)

Das laufende Ergebnis ist: [1, 2, 3, 5, 8, 9], das heißt, die Arrays werden in der Reihenfolge von klein bis sortiert angeordnet groß.

Im obigen Code wird die Funktion merge verwendet, um zwei sortierte Unterarrays zusammenzuführen. Zuerst definieren wir ein leeres Array result, um das zusammengeführte geordnete Array zu speichern. Verwenden Sie dann zwei Zeiger i und j, um auf die Startpositionen des linken bzw. rechten Subarrays zu zeigen, und vergleichen Sie die Elementgrößen des linken und rechten Subarrays. Wenn die Elemente des linken Subarrays kleiner sind als die Elemente des rechten Subarrays, fügen Sie die Elemente des linken Subarrays zum Array result hinzu und erhöhen Sie andernfalls i um 1; , fügen Sie die Elemente des rechten Subarrays zum Array result hinzu. Die Elemente werden zum Array result hinzugefügt und j wird um 1 erhöht. Fügen Sie abschließend die verbleibenden Elemente im linken oder rechten Subarray zum result-Array hinzu. Schließlich gibt die Funktion merge das zusammengeführte sortierte Array zurück. merge函数用于合并两个已排序的子数组。首先，我们定义一个空数组result用于存放合并后的有序数组。然后，使用两个指针i和j分别指向左子数组和右子数组的起始位置，并比较左右子数组的元素大小。如果左子数组的元素小于右子数组的元素，将左子数组的元素加入result数组，并将i自增1；否则，将右子数组的元素加入result数组，并将j自增1。最后，将左子数组或右子数组中剩余的元素加入result数组。最后，merge函数返回合并后的有序数组。

merge_sort函数用于归并排序的递归操作。对于一个给定的待排序数组arr，首先判断数组的长度是否小于等于1，如果是，则直接返回该数组。否则，通过len(arr) // 2找到数组的中间位置，并将数组拆分为两个子数组left和right。然后，分别对left和right递归调用merge_sort

merge_sort-Funktion wird für rekursive Operationen der Zusammenführungssortierung verwendet. Damit ein bestimmtes Array arr sortiert werden soll, ermitteln Sie zunächst, ob die Länge des Arrays kleiner oder gleich 1 ist, und wenn ja, geben Sie das Array direkt zurück. Andernfalls ermitteln Sie die mittlere Position des Arrays über len(arr) // 2 und teilen Sie das Array in zwei Unterarrays left und right auf. Rufen Sie dann rekursiv die Funktion merge_sort auf links und rechts auf, um die beiden erhaltenen sortierten Unterarrays zusammenzuführen und das zusammengeführte geordnete Array zurückzugeben.

Das Obige sind die spezifischen Schritte und Codebeispiele für die Verwendung von Python zur Implementierung des Zusammenführungssortierungsalgorithmus. Ich hoffe, es wird den Lesern helfen, den Zusammenführungssortierungsalgorithmus zu verstehen. 🎜

Das obige ist der detaillierte Inhalt vonWie implementiert man einen Merge-Sort-Algorithmus mit Python?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!