|
Le tri est traditionnellement une tâche difficile en informatique . Le choix d'un algorithme de tri qui est efficace et rapide peut être difficile. Souvent , le choix de l'algorithme efficace implique la connaissance des données qui sont triées, et trie spécialisés travaillent habituellement beaucoup mieux que les algorithmes de tri généralisé . Cependant, certaines espèces , comme le " tri par fusion , " peuvent travailler dans des situations généralisées en brisant les jeux et le tri des petits morceaux de manière récursive. La liste
Un tri par fusion est un " diviser pour régner " algorithme , en ce qu'elle prend des portions des listes et leur casse en permanence en deux moitiés jusqu'à atteindre les éléments uniques de la liste , qui sont ensuite fusionnées en commande. Par exemple, commencer avec une liste numérique comme
5 6 2 4 1 9 8 3 7 Photos Tri d'une liste comme celle-ci avec un tri par fusion , il faudra réduire de moitié la taille de la liste jusqu'à ce que chaque numéro de base seul existe . Ensuite, le tri peut comparer les chiffres et les mettre ensemble dans le bon ordre (plus bas au plus élevé, dans ce cas) .
La fusion Méthode
la méthode Merge est simple:
def fusion (premier, deuxième )
Prendre deux listes , la méthode de les fusionner en commençant au début de chaque liste. Il ajoute ensuite la prochaine montant minimum de chaque liste dans une nouvelle liste . Le résultat est une liste triée. ( Rappelez-vous de bien insérer un espace blanc de tabulation après le " tout " et " if /else " énoncés . ) :
Tout i < len ( premier ) et j < len ( seconde) :
< p> si le premier [ i ] < = seconde [j] :
new_list.append ( premier [i])
i = i + 1
autre :
new_list.append ( deuxième [ j])
j = j + 1}
Enfin, après une seule liste extrémités , les valeurs restantes sont placées dans la nouvelle liste :
new_list + = premier [ i: ]
new_list + = seconde [ j : ]
retour end_list
tri par fusion Conditions
le tri par fusion réelle entraîne l' algorithme de tri principal . Il ya deux parties fonctionnelles principales : l'aspect conditionnel qui arrête la récursivité une fois que les listes sont divisées et la récursion réelle qui réduit de moitié les listes. L' état d'arrêt vient en premier :
def mergesort ( liste):
if len ( liste) == 1:
retour Liste Cela garantit que quand une liste sous atteigne un seul élément , cet élément est retourné afin qu'il soit fusionné avec les autres numéros .
Merge Trier récursivité
La seconde moitié du le tri est la récursivité. Après le "if" /conditionnel , comme suit:
autre :
milieu = len ( liste) /2
start = mergesort ( liste [ milieu : ] ) Photos end = mergesort ( liste [: milieu ] )
retour fusion ( début, fin )
raison de récursivité, après que les listes sont divisées en éléments simples, l'algorithme pistes remonter à la dernière méthode exécutée . Donc , au moment où la déclaration «retour fusion ( début, fin ) " exécute , l'algorithme renvoie une fusion , une liste triée des deux listes triées , précédemment fusionnées de plus petite taille .
|
