Tri de Shell en Python
Exemples Python3Le tri de Shell, également connu sous le nom d'algorithme de tri par incréments décroissants, est une version améliorée plus efficace du tri par insertion. Cependant, le tri de Shell est un algorithme de tri instable.
L'idée de base du tri de Shell est la suivante : diviser d'abord toute la séquence d'enregistrements à trier en plusieurs sous-séquences et effectuer un tri par insertion directe sur chaque sous-séquence séparément. Lorsque les enregistrements de toute la séquence sont « pratiquement ordonnés », effectuer ensuite un tri par insertion directe sur tous les enregistrements séquentiellement.
Exemple
def shellSort(arr):
n = len(arr)
gap = int(n/2)
while gap > 0:
for i in range(gap,n):
temp = arr[i]
j = i
while j >= gap and arr[j-gap] >temp:
arr[j] = arr[j-gap]
j -= gap
arr[j] = temp
gap = int(gap/2)
arr = [ 12, 34, 54, 2, 3]
n = len(arr)
print ("Avant le tri :")
for i in range(n):
print(arr[i]),
shellSort(arr)
print ("\nAprès tri :")
for i in range(n):
print(arr[i]),
L'exécution du code ci-dessus produit le résultat suivant :
排序前: 12 34 54 2 3 排序后: 2 3 12 34 54Autres extensions