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

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

L'algorithme de tri par base est un algorithme de tri non comparatif qui complète le tri en divisant les éléments à trier en un ensemble limité de chiffres. En C++, nous pouvons utiliser l’algorithme de tri par base pour trier un ensemble d’entiers. Ci-dessous, nous verrons en détail comment implémenter l'algorithme de tri par base, avec des exemples de code spécifiques.

1. Idée d'algorithme
   L'idée de l'algorithme de tri par base est de diviser les éléments à trier en un ensemble limité de bits numériques, puis de trier les éléments sur chaque bit tour à tour. Une fois le tri sur chaque bit terminé, les éléments sont réorganisés selon l'ordre de ce bit, puis le tri du bit suivant se poursuit jusqu'à ce que tous les bits soient triés.
2. Étapes spécifiques de mise en œuvre
   (1) Tout d'abord, nous devons déterminer le nombre de chiffres dans la valeur maximale parmi tous les éléments à trier. Cela déterminera le nombre de tours de tri que nous devrons effectuer.

(2) Ensuite, nous devons créer un tableau auxiliaire et un tableau de comptage. Le tableau auxiliaire est utilisé pour stocker les résultats temporaires pendant le processus de tri, et le tableau de comptage est utilisé pour enregistrer le nombre d'occurrences de chaque nombre.

(3) Ensuite, nous devons effectuer plusieurs tours de tri. Chaque cycle de tri réorganise le tableau en fonction de la taille actuelle en bits.

(4) À chaque tour de tri, nous devons parcourir le tableau à trier, utiliser la valeur binaire actuelle de chaque élément comme index et placer les éléments dans le compartiment correspondant.

(5) Ensuite, nous devons compter le nombre d'éléments dans chaque seau, qui peut être enregistré à l'aide d'un tableau de comptage.

(6) Ensuite, nous devons déterminer la position des éléments dans chaque compartiment du tableau auxiliaire en comptant le tableau. Cela peut être déterminé en comptant la somme des préfixes des éléments du tableau.

(7) Enfin, nous écrasons les éléments du tableau auxiliaire dans le tableau à trier pour terminer un tour de tri.

(8) Répétez les étapes (3) à (7) jusqu'à ce que tous les bits soient triés.

3. Exemple de code
   Ce qui suit est un exemple de code qui utilise C++ pour implémenter l'algorithme de tri par base :

#include <iostream>
#include <vector>

using namespace std;

void radixSort(vector<int>& arr) {
    int maxVal = *max_element(arr.begin(), arr.end());

    int digit = 1;
    vector<int> temp(arr.size());
    while (maxVal / digit > 0) {
        vector<int> count(10, 0);

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

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

        for (int i = arr.size() - 1; i >= 0; i--) {
            temp[count[(arr[i] / digit) % 10] - 1] = arr[i];
            count[(arr[i] / digit) % 10]--;
        }

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

        digit *= 10;
    }
}

int main() {
    vector<int> arr = { 170, 45, 75, 90, 802, 24, 2, 66 };
    radixSort(arr);

    cout << "排序结果：";
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Dans l'exemple de code ci-dessus, nous trouvons d'abord la valeur maximale dans le tableau à trier pour déterminer le nombre de tours de un tri est nécessaire. Ensuite, nous avons créé un tableau auxiliaire et un tableau de comptage. Ensuite, nous effectuons plusieurs tours de tri pour réassembler le tableau en fonction de la taille de bits actuelle. Enfin, nous générons les résultats triés.

Résumé :
Avec l'algorithme de tri par base, nous pouvons trier un ensemble d'entiers en C++. L'idée principale de l'algorithme de tri par base est de diviser les éléments à trier en un ensemble limité de bits numériques, puis de trier les éléments sur chaque bit tour à tour. Cet algorithme de tri non comparatif peut gérer efficacement le problème de tri d'un ensemble d'entiers.

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!