Quels sont les algorithmes de tri en Python ?

王林
Libérer: 2023-10-18 09:06:32
original
1176 Les gens l'ont consulté

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
Copier après la connexion
  1. 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
Copier après la connexion
  1. 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
Copier après la connexion
  1. 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)
Copier après la connexion
  1. 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
Copier après la connexion
  1. 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
Copier après la connexion

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!

Étiquettes associées:
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal