Quels sont les algorithmes de tri en Python ?

Les algorithmes de tri couramment utilisés en Python incluent le tri à bulles, le tri par insertion, le tri par sélection, le tri rapide, le tri par fusion et le tri par tas. Les principes de ces algorithmes de tri seront présentés ci-dessous et des exemples de codes correspondants seront donnés.

1. Tri à bulles :
   Le tri à bulles est un algorithme de tri simple et intuitif. Il parcourt à plusieurs reprises la liste à trier, en comparant les tailles de deux éléments adjacents et en déplaçant le plus grand élément vers l'arrière. Lors de chaque itération, le plus grand élément « bulle » jusqu'à la fin de la liste.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

2. Tri par insertion :
   L'idée de base du tri par insertion est d'insérer les éléments à trier à la bonne position un par un dans la liste triée. Le tri par insertion commence à partir du deuxième élément, compare chaque élément à la liste triée précédente et l'insère à la position appropriée.

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

3. Tri par sélection :
   Le tri par sélection parcourt la liste à chaque fois, trouve le plus petit élément et l'échange avec la position actuelle. Continuez à répéter ce processus jusqu'à ce que la liste entière soit triée.

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

4. Tri rapide :
   Quick Sort est un algorithme de tri efficace. Il utilise l'idée de Diviser et Conquérir pour diviser une liste en deux sous-listes, puis trier récursivement les sous-listes.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

5. Tri par fusion :
   Le tri par fusion divise la liste en deux sous-listes, trie chaque sous-liste, puis fusionne les sous-listes triées ensemble.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

6. Tri par tas :
   Le tri par tas est un algorithme de tri par sélection arborescente qui utilise les propriétés des tas binaires pour le tri. Les tas peuvent être divisés en tas max et tas min. Le nœud racine du tas max est le plus grand élément et le nœud racine du tas min est le plus petit élément.

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[i] < arr[left]:
        largest = left
    if right < n and arr[largest] < arr[right]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)
    return arr

Ci-dessus sont plusieurs algorithmes de tri couramment utilisés en Python, et des exemples de code correspondants sont fournis. Différents algorithmes de tri conviennent à différentes situations et tailles de données. Le choix d'un algorithme de tri approprié en fonction de la situation réelle peut améliorer l'efficacité opérationnelle du programme.

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!