Maison >développement back-end >C++ >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 :
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!