Comment implémenter un algorithme de tri par fusion à l'aide de Python ?

Comment implémenter l'algorithme de tri par fusion en utilisant Python ?

Merge Sort est un algorithme de tri courant qui utilise l'idée de diviser pour régner pour diviser un gros problème en plusieurs petits problèmes à résoudre, puis fusionner les solutions aux petits problèmes. La complexité temporelle du tri par fusion est O(nlogn) et convient aux ensembles de données de différentes tailles.

Ci-dessous, nous présenterons en détail comment utiliser Python pour implémenter l'algorithme de tri par fusion et donnerons des exemples de code spécifiques.

L'idée de base du tri par fusion est de diviser le tableau à trier en deux sous-tableaux, puis de trier chaque sous-tableau séparément, et enfin de fusionner les sous-tableaux triés. Les étapes spécifiques sont les suivantes :

1. Divisez continuellement le tableau à trier en deux sous-tableaux jusqu'à ce que chaque sous-tableau ne contienne qu'un seul élément. Ceci peut être réalisé grâce à la récursion.
2. Triez chaque sous-tableau, vous pouvez utiliser la récursivité ou l'itération.
3. Combinez les sous-tableaux triés pour former le tableau ordonné final.

Ce qui suit est un exemple de code pour implémenter le tri par fusion en 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)

Le résultat en cours d'exécution est : [1, 2, 3, 5, 8, 9], c'est-à-dire que les tableaux sont classés du plus petit au plus petit. grand.

Dans le code ci-dessus, la fonction merge est utilisée pour fusionner deux sous-tableaux triés. Tout d’abord, nous définissons un tableau vide result pour stocker le tableau ordonné fusionné. Ensuite, utilisez deux pointeurs i et j pour pointer respectivement vers les positions de départ du sous-tableau gauche et du sous-tableau droit, et comparez les tailles d'éléments des sous-tableaux gauche et droit. Si les éléments du sous-tableau gauche sont plus petits que les éléments du sous-tableau droit, ajoutez les éléments du sous-tableau gauche au tableau result, et incrémentez i de 1 sinon ; , ajoutez les éléments du sous-tableau de droite au tableau result. Les éléments sont ajoutés au tableau result et j est incrémenté de 1. Enfin, ajoutez les éléments restants du sous-tableau gauche ou du sous-tableau droit au tableau result. Enfin, la fonction merge renvoie le tableau trié fusionné. 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

La fonction merge_sort est utilisée pour les opérations récursives de tri par fusion. Pour qu'un tableau arr donné soit trié, déterminez d'abord si la longueur du tableau est inférieure ou égale à 1, et si c'est le cas, renvoyez directement le tableau. Sinon, trouvez la position médiane du tableau via len(arr) // 2 et divisez le tableau en deux sous-tableaux left et right. Ensuite, appelez récursivement la fonction merge_sort sur gauche et droite pour fusionner les deux sous-tableaux triés obtenus et renvoyer le tableau ordonné fusionné.

Ci-dessus sont les étapes spécifiques et les exemples de code d'utilisation de Python pour implémenter l'algorithme de tri par fusion. J'espère qu'il sera utile aux lecteurs de comprendre l'algorithme de tri par fusion. 🎜

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!