Quels sont les algorithmes de tri des tableaux ?

L'algorithme de tri des tableaux est utilisé pour organiser les éléments dans un ordre spécifique. Les types courants d'algorithmes incluent : Tri à bulles : échangez les positions en comparant les éléments adjacents. Tri par sélection : recherchez le plus petit élément et remplacez-le par la position actuelle. Tri par insertion : insérez les éléments un par un à la bonne position. Tri rapide : méthode diviser pour mieux régner, sélectionnez l'élément pivot pour diviser le tableau. Tri par fusion : diviser pour mieux régner, tri récursif et fusion de sous-tableaux.

Introduction et pratique de l'algorithme de tri de tableaux

En informatique, l'algorithme de tri de tableaux est un algorithme utilisé pour organiser un ensemble d'éléments dans un ordre spécifique. Les algorithmes de tri sont divisés en de nombreux types différents en fonction de leurs principes et de leur efficacité. Ce qui suit présentera quelques algorithmes courants de tri de tableaux et démontrera leur utilisation à travers des cas pratiques.

Tri à bulles

Le tri à bulles est un algorithme de tri simple et facile à comprendre. Son principe de base est de comparer tour à tour les tailles des éléments adjacents, et si l'élément précédent est plus grand que l'élément suivant, d'échanger leurs tailles. postes. Ce processus est répété jusqu'à ce que tous les éléments soient en ordre.

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

Tri par sélection

Le tri par sélection est également un algorithme de tri simple. Son principe est de trouver le plus petit élément de la partie non triée et de l'échanger avec l'élément de position actuelle. Répétez ensuite le processus jusqu'à ce que tous les éléments soient en ordre.

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

Tri par insertion

Le tri par insertion est un algorithme de tri basé sur des opérations d'insertion. Son principe de base est d'insérer des éléments un par un dans la position correcte de la partie triée jusqu'à ce que tous les éléments soient disposés dans l'ordre.

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

Quicksort

Quicksort est un algorithme de tri diviser pour régner qui fonctionne en divisant un tableau en deux sous-tableaux en sélectionnant un élément pivot, puis en triant récursivement les deux sous-tableaux jusqu'à ce que tous les éléments soient en ordre.

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)

Tri par fusion

Le tri par fusion est un algorithme de tri diviser pour régner stable et efficace. Son principe est de diviser récursivement le tableau en sous-tableaux plus petits, puis de trier et de fusionner les sous-tableaux jusqu'à ce que tous les éléments soient présents. Disposé dans l'ordre.

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

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

Cas pratique

Supposons que nous ayons une liste non ordonnée arr = [5, 2, 8, 3, 1, 9], nous pouvons utiliser l'algorithme de tri rapide pour la trier, le code est le suivant :

arr = [5, 2, 8, 3, 1, 9]
sorted_arr = quick_sort(arr)
print(sorted_arr)  # 输出：[1, 2, 3, 5, 8, 9]

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!