Introduction détaillée aux étapes d'implémentation de l'algorithme de tri par fusion en programmation Python

Idée de base : le tri par fusion est une idée typique de diviser pour régner, qui divise une liste non ordonnée en deux, puis divise à nouveau chaque sous-séquence en deux et continue jusqu'à ce qu'elle ne puisse plus être divisée. Ensuite, le processus de fusion commence, comparant les éléments de chaque sous-séquence avec une autre sous-séquence, et plaçant séquentiellement les petits éléments dans la séquence de résultats pour la fusion, et enfin en complétant le tri de fusion.

Processus d'opération de fusion :

Demander de l'espace pour que sa taille soit la somme des deux séquences triées. Cet espace est utilisé pour stocker la séquence fusionnée.
Définissez deux pointeurs, les positions initiales sont respectivement les positions de départ des deux séquences triées
Comparez les éléments pointés par les deux pointeurs, sélectionnez l'élément relativement petit et placez-le dans l'espace de fusion, puis déplacez le pointeur à la position suivante
Répétez l'étape 3 jusqu'à ce qu'un certain pointeur atteigne la fin de la séquence
Copiez tous les éléments restants de l'autre séquence directement à la fin de la séquence fusionnée
La déclaration ci-dessus est une déclaration théorique . Voici un exemple pratique pour illustrer :

Par exemple, un tableau non ordonné

[6,2,3,1,7]

Décomposez d'abord le tableau de manière récursive jusqu'à :

[6],[2],[3],[1],[7]

Ensuite, lancez le tri par fusion, également de manière récursive :

fusionnez et triez deux par deux, obtenez :

[2,6],[1,3],[7]

Dans l'étape précédente, il a en fait été fusionné de la même manière que cette étape, mais comme il y a un numéro dans chaque liste, le processus ne peut pas être entièrement affiché. Le processus peut être entièrement illustré ci-dessous.

Initial :

 a = [2,6] b = [1,3] c = []

Étape 1, retirez séquentiellement un numéro de a, b : 2, 1, comparez la taille et mettez-le Entrez c et supprimez le numéro de la liste d'origine Le résultat est :

a = [2,6] b = [3] c = [1]

Étape 2, continuez à partir de a, b dans l'ordre Sortir. le numéro, c'est-à-dire répétez les étapes ci-dessus, cette fois c'est : 2,3. Comparez la taille et mettez-la dans c, et supprimez le numéro de la liste d'origine. Le résultat est :

a = [6] b = [3] c = [1,2]

Étape 3, répétez les étapes précédentes, le résultat est :

a = [6] b = [] c = [1,2,3]

La dernière étape est pour annexer 6 à c , le résultat est :

a = [] b = [] c = [1,2,3,6]

En appliquant de manière répétée le processus ci-dessus, la fusion de [1,2,3,6] et [7] est obtenu

Obtenir enfin le résultat du tri

[1,2,3,6,7]

Cet article répertorie trois méthodes d'implémentation Python :

Méthode 1 : Traduire le processus décrit ci-dessus, un peu maladroitement

#! /usr/bin/env python
#coding:utf-8

def merge_sort(seq):
 if len(seq) ==1:
 return seq
 else:
 middle = len(seq)/2
 left = merge_sort(seq[:middle])
 right = merge_sort(seq[middle:])

 i = 0 #left 计数
 j = 0 #right 计数
 k = 0 #总计数

 while i < len(left) and j < len(right):
  if left[i] < right [j]:
  seq[k] = left[i]
  i +=1
  k +=1
  else:
  seq[k] = right[j]
  j +=1
  k +=1

 remain = left if i<j else right
 r = i if remain ==left else j

 while r<len(remain):
  seq[k] = remain[r]
  r +=1
  k +=1

 return seq

Méthode 2 : En termes de prise de valeurs ​​dans l'ordre, appliquez Sans la méthode list.pop(), le code est plus compact et concis

#! /usr/bin/env python
#coding:utf-8


def merge_sort(lst): #此方法来自维基百科

 if len(lst) <= 1:
 return lst

 def merge(left, right):
 merged = []

 while left and right:
  merged.append(left.pop(0) if left[0] <= right[0] else right.pop(0))

 while left:
  merged.append(left.pop(0))

 while right:
  merged.append(right.pop(0))

 return merged

 middle = int(len(lst) / 2) 
 left = merge_sort(lst[:middle])
 right = merge_sort(lst[middle:])
 return merge(left, right)

Méthode 3 : Ça tourne Sachez que la fusion est fournie dans le module python heapq. Pour la méthode de tri, importez simplement les résultats décomposés dans cette méthode.

#! /usr/bin/env python
#coding:utf-8


from heapq import merge

def merge_sort(seq):
 if len(seq) <= 1:
 return m
 else:  
 middle = len(seq)/2
 left = merge_sort(seq[:middle])
 right = merge_sort(seq[middle:])
 return list(merge(left, right))  #heapq.merge()

if __name__=="__main__":
 seq = [1,3,6,2,4]
 print merge_sort(seq)

Pour une introduction plus détaillée aux étapes de mise en œuvre de l'algorithme de tri par fusion dans la programmation Python, veuillez faire attention au site Web PHP chinois !