Comment écrire un algorithme de tri par insertion en Python ?

Comment écrire un algorithme de tri par insertion en Python ?

Le tri par insertion est un algorithme de tri simple et intuitif. Son idée est de diviser le tableau à trier en une partie ordonnée et une partie non ordonnée. À chaque fois, un élément est sélectionné dans la partie non ordonnée et inséré dans la position correcte de la partie non ordonnée. pièce commandée. L'implémentation de l'algorithme de tri par insertion est généralement implémentée en comparant et en échangeant des éléments plusieurs fois, avec une complexité temporelle de O(n^2).

Voyons comment écrire l'algorithme de tri par insertion en Python, ainsi que des exemples de code spécifiques.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]              # 当前待插入元素
        j = i - 1                 # 有序部分的最后一个元素索引

        # 将比key大的元素都向后移动一位
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key           # 将key插入正确位置

    return arr

Ce qui précède est le code d'implémentation spécifique de l'algorithme de tri par insertion. Dans la fonction principale, nous devons transmettre un tableau arr à trier et renvoyer le résultat trié.

Dans la boucle principale de l'algorithme, on part du deuxième élément et on l'utilise comme clé de l'élément à insérer. Nous comparons ensuite la clé avec le dernier élément de la pièce triée et déplaçons l'élément plus grand que la clé d'une position vers l'arrière jusqu'à ce que nous trouvions la position correcte de la clé. Enfin, nous insérons la clé au bon endroit.

Ensuite, nous pouvons tester cet algorithme de tri par insertion.

arr = [9, 5, 1, 6, 8, 2]
sorted_arr = insertion_sort(arr)
print(sorted_arr)

Le résultat de sortie est :

[1, 2, 5, 6, 8, 9]

Vous pouvez voir que grâce à l'algorithme de tri par insertion, nous avons réussi à organiser le tableau d'entrée par ordre croissant.

Pour résumer, écrire l'algorithme de tri par insertion en Python n'est pas compliqué. Il nous suffit de comprendre l'idée de base du tri par insertion, puis d'implémenter le code correspondant basé sur l'idée. Bien entendu, pour rendre le code plus robuste et polyvalent, nous pouvons également gérer des cas extrêmes, tels que des tableaux vides ou des tableaux avec un seul élément.

J'espère que cet article pourra vous aider à comprendre et à maîtriser l'algorithme de tri par insertion !

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!