Comment utiliser l'algorithme de tri par insertion en C++

Utilisez l'algorithme de tri par insertion en C++ pour implémenter le tri par tableau

Le tri par insertion est un algorithme de tri simple mais efficace qui insère les éléments à trier un par un dans la liste triée et obtient finalement une liste ordonnée. Cet article explique comment utiliser le langage de programmation C++ pour implémenter l'algorithme de tri par insertion et donne des exemples de code spécifiques.

Idée d'algorithme :
L'idée de base du tri par insertion est de diviser le tableau en intervalles triés et en intervalles non triés. Chaque fois qu'un élément est sélectionné dans la plage non triée et inséré dans la position appropriée de la plage triée jusqu'à ce que la plage non triée soit vide.

Étapes spécifiques :

1. Parcourez le tableau et insérez les éléments de l'intervalle non trié dans l'intervalle trié en séquence.
2. Pour chaque élément de la plage non triée, comparez-le avec les éléments de la plage triée afin de trouver la position d'insertion.
3. Insérez l'élément dans la position appropriée de l'intervalle trié et déplacez les éléments de l'intervalle trié d'une position vers l'arrière.

Exemple de code :
Ce qui suit est un exemple de code qui utilise le langage de programmation C++ pour implémenter l'algorithme de tri par insertion :

#include <iostream>

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = { 5, 2, 4, 6, 1, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);

    std::cout << "原始数组：";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    insertionSort(arr, n);

    std::cout << "排序后的数组：";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

Dans le code ci-dessus, nous définissons une fonction nommée insertionSort的函数来实现插入排序。在main函数中，我们定义了一个待排序的数组并调用insertionSort pour le tri. Enfin, nous affichons les résultats triés sur la console.

Résultats d'exécution :
Tableau d'origine : 5 2 4 6 1 3
Tableau trié : 1 2 3 4 5 6

Résumé :
Grâce à l'exemple de code ci-dessus, nous pouvons voir comment utiliser l'algorithme de tri par insertion en C++ pour trier le tableau. Bien que le tri par insertion soit simple, sa complexité temporelle est O(n^2) et son efficacité de tri pour les données à grande échelle est faible. Dans les applications pratiques, si une grande quantité de données doit être triée, il est recommandé d'utiliser un algorithme de tri plus efficace, tel qu'un tri rapide ou un tri par fusion.

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!