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

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

L'algorithme de tri par comptage est un algorithme de tri relativement simple et efficace, adapté aux scénarios dans lesquels des séquences entières sont triées. Son idée de base est de déterminer combien d'éléments avant chaque élément sont plus petits que lui, déterminant ainsi sa position dans le tableau ordonné.

Les étapes de l'algorithme de tri par comptage sont les suivantes :

1. Trouver la valeur maximale dans le tableau à trier pour déterminer la longueur du tableau de comptage.
2. Créez un tableau de comptage avec une longueur égale à la valeur maximale plus un et initialisez-le à 0.
3. Parcourez le tableau à trier, comptez le nombre d'occurrences de chaque élément et enregistrez les résultats statistiques dans le tableau de comptage.
4. Transformez le tableau de comptage afin que la valeur de chaque position soit égale à la somme de ses valeurs de position précédentes.
5. Créez un tableau temporaire de la même longueur que le tableau à trier pour enregistrer les résultats du tri.
6. Parcourez le tableau à trier d'arrière en avant, déterminez la position de chaque élément dans le résultat trié en fonction du tableau de nombre et stockez les éléments dans un tableau temporaire.
7. Copiez les résultats du tableau temporaire dans le tableau à trier pour terminer le tri.

Ce qui suit est un exemple de code d'un algorithme de tri par comptage implémenté en langage C++ :

#include <iostream>
#include <vector>

using namespace std;

void countingSort(vector<int>& arr) {
    int max_val = arr[0];
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i] > max_val) {
            max_val = arr[i];
        }
    }

    vector<int> count(max_val + 1, 0);

    for (int i = 0; i < arr.size(); i++) {
        count[arr[i]]++;
    }

    for (int i = 1; i < count.size(); i++) {
        count[i] += count[i - 1];
    }

    vector<int> temp(arr.size());
    for (int i = arr.size() - 1; i >= 0; i--) {
        temp[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    for (int i = 0; i < arr.size(); i++) {
        arr[i] = temp[i];
    }
}

int main() {
    vector<int> arr = {5, 1, 4, 3, 2};
    countingSort(arr);

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

    return 0;
}

Dans le code ci-dessus, nous utilisons un tableau de comptage auxiliaire pour compter le nombre d'occurrences de chaque élément, puis calculons le nombre d'occurrences de chaque élément par déformation Position dans les résultats triés. Enfin, nous copions les résultats triés dans le tableau d'origine.

Grâce à l'exemple de code ci-dessus, nous pouvons voir le processus de mise en œuvre de l'algorithme de tri par comptage. Sa complexité temporelle est O(n+k), où n est la longueur de la séquence à trier et k est la somme des valeur maximale de l'élément et valeur minimale de l'élément. La différence est de plus un.

Pour résumer, l'algorithme de tri par comptage est un algorithme de tri simple mais efficace adapté aux scénarios où des séquences entières sont triées. En utilisant des structures de données et des algorithmes appropriés, nous pouvons mieux accomplir la tâche de tri.

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!