Tri à bulles en Python
Exemples Python3Le tri à bulles est un simplealgorithme de tri par échange, et son principe de fonctionnement essentiel est :
- Parcourir à plusieurs reprises la liste à trier, en comparantdeux éléments adjacents；
- Si l'ordre des deux éléments ne répond pas aux exigences (par exemple, dans un tri croissant, l'élément précédent est supérieur au suivant), alorséchanger leurs positions；
- Chaque tour de parcours déplacera leplus grand élément de la partie non triée actuelle vers la fin par remontée(scénario d'ordre croissant), tout comme des bulles qui remontent ;
- Répéter le processus ci-dessus jusqu'à ce que la liste entière soit complètement triée (aucune opération d'échange ne se produit ou tous les éléments ont été parcourus).
Caractéristiques clés
- Type de tri : tri par échange
- Complexité temporelle : pire cas O(n²) (liste complètement en ordre inverse), cas moyen O(n²), meilleur cas O(n) (version optimisée, liste déjà triée)
- Complexité spatiale : O(1) (tri sur place, aucun espace auxiliaire supplémentaire nécessaire)
- Stabilité : tri stable (les positions relatives des éléments égaux ne changeront pas)
Exemple
def bubbleSort(arr):
n = len(arr)
# Parcourir tous les éléments du tableau
for i in range(n):
# Les i derniers éléments sont déjà à la bonne position (pas besoin de comparer à nouveau)
for j in range(0, n-i-1):
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
arr = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(arr)
print ("Tableau trié :")
for i in range(len(arr)):
print ("%d" %arr[i]),
La sortie de l'exécution du code ci-dessus est :
排序后的数组: 11 12 22 25 34 64 90Autres extensions