Maison > développement back-end > C++ > Quels sont les algorithmes de tri des tableaux ?

Quels sont les algorithmes de tri des tableaux ?

WBOY
Libérer: 2024-06-02 22:33:59
original
713 Les gens l'ont consulté

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.

Quels sont les algorithmes de tri des 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]
Copier après la connexion

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]
Copier après la connexion

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

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

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

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]
Copier après la connexion

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