Comment trier en python

Les méthodes de tri Python incluent le tri à bulles, le tri par sélection, le tri par insertion, le tri rapide, le tri par fusion, le tri par tas, le tri par base, etc. Introduction détaillée : 1. Tri par bulles, tri en comparant les éléments adjacents et en échangeant leurs positions ; 2. Tri par sélection, tri en trouvant le plus petit élément de la liste et en le plaçant à la fin de la partie triée ; insérer chaque élément dans la position appropriée de la partie triée ; 4. Tri rapide, en utilisant la méthode diviser pour régner pour diviser la liste en sous-listes plus petites, etc.

Le système d'exploitation de ce tutoriel : système Windows 10, Python version 3.11.4, ordinateur Dell G3.

Python est un langage de programmation puissant qui fournit plusieurs méthodes de tri pour trier les données. Dans cet article, nous aborderons au moins 7 méthodes de tri différentes, avec des exemples de code détaillés.

1. Tri à bulles :

Le tri à bulles est un algorithme de tri simple qui trie en comparant les éléments adjacents et en échangeant leurs positions. Il parcourt la liste à plusieurs reprises jusqu'à ce qu'aucun échange ne se produise.

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

2. Tri par sélection :

Le tri par sélection est un algorithme de tri simple qui trie en trouvant le plus petit élément de la liste et en le plaçant à la fin de la partie triée.

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

3. Tri par insertion :

Le tri par insertion est un algorithme de tri simple qui trie en insérant chaque élément dans la position appropriée de la partie trié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

4. Tri rapide :

Le tri rapide est un algorithme de tri efficace qui utilise la méthode diviser pour régner pour diviser une liste en sous-listes plus petites, puis trier les sous-listes de manière récursive.

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 est un algorithme de tri efficace qui utilise la méthode diviser pour régner pour diviser la liste en sous-listes plus petites, puis trier récursivement les sous-listes, et enfin elles sont combinées en une liste ordonnée.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    left = merge_sort(left)
    right = merge_sort(right)
    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. Heap Sort :

Le tri par tas est un algorithme de tri efficace qui utilise une structure de données de tas binaire pour le tri.

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[i] < arr[l]:
        largest = l
    if r < n and arr[largest] < arr[r]:
        largest = r
    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

7. Radix Sort :

Le tri Radix est un algorithme de tri non comparatif qui trie les éléments en fonction du nombre de chiffres.

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    for i in range(n):
        index = arr[i] // exp
        count[index % 10] += 1
    for i in range(1, 10):
        count[i] += count[i-1]
    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1
    for i in range(n):
        arr[i] = output[i]
def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        counting_sort(arr, exp)
        exp *= 10
    return arr

Voici des exemples de code détaillés de 7 méthodes de tri différentes. Selon différents ensembles de données et exigences de performances, le choix d'un algorithme de tri approprié peut améliorer l'efficacité et les performances du code

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!