Explication détaillée d'analyses simples et exemples de code d'utilisation de l'algorithme de tri par insertion en Python

Description du problème

Réorganisez un ensemble de nombres disposés de manière aléatoire, du plus petit au plus grand.

Algorithme d'insertion

Prend un numéro du tableau à la fois, le compare avec le numéro existant et l'insère dans la position appropriée.

Répétez de cette façon, chaque fois que vous pouvez conserver les numéros existants dans l'ordre jusqu'à ce que les numéros soient supprimés, c'est-à-dire que le tri soit réussi.

Ceci est très similaire à la situation de tirage de cartes lorsque vous jouez aux cartes,

La première condition : Gardez l'ordre correct des cartes dans votre main
La deuxième condition : Piochez-en de nouvelles tous les temps Les cartes sont insérées au milieu des cartes dans la main dans l'ordre.
Gardez ces deux éléments inchangés, peu importe le nombre de cartes que vous piochez, les dernières cartes de votre main seront classées dans l'ordre.

Implémentation Python :

def insertion_sort(n):
 if len(n) == 1:
  return n
 b = insertion_sort(n[1:])
 m = len(b)
 for i in range(m):
  if n[0] <= b[i]:
   return b[:i]+[n[0]]+b[i:]
 return b + [n[0]]

Une autre version :

def insertion_sort(lst):
 if len(lst) == 1:
  return lst

 for i in xrange(1, len(lst)):
  temp = lst[i]
  j = i - 1
  while j >= 0 and temp < lst[j]:
   lst[j + 1] = lst[j]
   j -= 1
  lst[j + 1] = temp
 return lst

Pour des explications plus détaillées sur des analyses simples et des exemples de code d'utilisation de l'algorithme de tri par insertion en Python, veuillez prêter attention au PHP Site chinois !