Comment implémenter le tri par fusion à l'aide de Python

Le tri par fusion est un algorithme de tri classique. Son idée principale est de diviser le tableau à trier en plusieurs sous-tableaux, de trier ces sous-tableaux et enfin de fusionner les sous-tableaux triés en un tableau ordonné. Le tri par fusion est un algorithme de tri relativement efficace avec une complexité temporelle de O(nlogn).

Dans cet article, nous expliquerons comment implémenter le tri par fusion en Python.

1. L'idée de​​implémenter le tri par fusion

L'idée de​​mettre en œuvre le tri par fusion comprend deux parties, à savoir diviser pour mieux régner et fusionner. Les étapes spécifiques de mise en œuvre sont les suivantes :

1) Continuez à diviser le tableau à trier en deux et triez récursivement les parties gauche et droite.

2) Fusionnez les parties gauche et droite triées dans un tableau ordonné ;

2. Utilisez Python pour implémenter diviser pour régner

Diviser pour régner est l'idée centrale du tri par fusion. Nous devons d'abord implémenter la partie diviser pour régner.

Le code est le suivant :

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)

Dans cette fonction, on détermine d'abord si la longueur du tableau est inférieure ou égale à 1, puis on renvoie directement le tableau. Sinon, nous devons diviser le tableau en deux, trier récursivement les parties gauche et droite respectivement, et enfin fusionner les parties gauche et droite triées.

2.1 Mettre en œuvre la fusion

Sur la base de la division et de la conquête, nous devons mettre en œuvre la partie fusion.

Le code est le suivant :

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

Dans cette fonction, on initialise d'abord les pointeurs i et j, qui pointent vers les éléments à comparer respectivement dans les parties gauche et droite. Ensuite, nous comparons continuellement les éléments gauche et droit, ajoutons le plus petit élément à la liste de résultats et déplaçons le pointeur vers la droite. Enfin, nous ajoutons également tous les éléments restants à la liste résultante afin d'obtenir un tableau trié.

3. Code complet

Combinant les parties diviser pour mieux régner et fusionner, le code complet est le suivant :

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

4. Test

Afin de vérifier que notre code de tri de fusion est correct, nous devons effectuer un test .

Le code est le suivant :

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

Le résultat de sortie est :

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

Les résultats du test montrent que notre code de tri de fusion est correct.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!