Introduction à la méthode de tri par fusion à l'aide de la programmation Python

Cet article présente principalement le code spécifique de la pythonprogrammation pour réaliser le tri par fusion. Il a une certaine valeur de référence. Les amis intéressés peuvent s'y référer

En raison de. une question sur leetcode la semaine dernière (Médiane de deux Sorted Arrays), je voulais examiner de plus près l'implémentation du tri par fusion.

Permettez-moi d'abord d'expliquer l'idée du tri :

Tout d'abord, le tri par fusion utilise la méthode de la dichotomie. En dernière analyse, l'idée est de diviser pour mieux régner. Obtenez un long tableau, divisez-le en parties gauche et droite en continu, puis divisez-le de manière récursive. Fusionnez-les ensuite en deux tableaux ordonnés. Cela peut être difficile à comprendre de cette façon, je vais donc vous donner une image que j'ai dessinée.

Cela montre la première étape du tri par fusion. Le tableau est divisé de manière récursive selon le milieudle, et finalement divisé dans les plus petits détails. trie deux tableaux triés en utilisant la même méthode que pour les trier.

La méthode de tri de deux tableaux ordonnés est très simple. Comparez les premières positions des deux tableaux en même temps, placez le plus petit dans un tableau vide, puis placez-le. le pointeur sur la position du tableau vide est reculé d'un point, puis continue d'être comparé à la position précédente de l'autre tableau, et ainsi de suite. Lorsque le dernier tableau est retiré de la pile en premier, tous les éléments de l'autre tableau seront ajoutés au nouveau tableau.

Puisque la complexité temporelle de la division récursive est logN, cependant, la complexité de la méthode de tri de deux tableaux ordonnés est N. La complexité temporelle de cet algorithme est N*logN, donc c'est NlogN.

Selon cette vague d'analyse, nous pouvons examiner un comportement de l'image ci-dessus.

Lorsque la partie la plus à gauche est divisée en les plus petits détails, elle ne peut plus être divisée en parties gauche et droite puis fusionner.

La première combinaison complète la fusion de [4, 7]

La deuxième combinaison complète la fusion de [4, 7, 8]

La troisième combinaison complète[ Le fusion de 3, 5]

La quatrième combinaison est terminée La fusion de [3, 5, 9]

La cinquième combinaison est terminée [3, 4, 5, 7, 8, 9 ] La fusion termine le tri.

Mettez le code python ci-dessous

def merge(a, b):
 c = []
 h = j = 0
 while j < len(a) and h < len(b):
  if a[j] < b[h]:
   c.append(a[j])
   j += 1
  else:
   c.append(b[h])
   h += 1

 if j == len(a):
  for i in b[h:]:
   c.append(i)
 else:
  for i in a[j:]:
   c.append(i)

 return c


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


if name == &#39;main&#39;:
 a = [4, 7, 8, 3, 5, 9]
 print merge_sort(a)

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!