Le rythme de comptage est un algorithme de tri stable. Count Tri utilise un tableau supplémentaire Count_Arr, où le i-th element est le nombre d'éléments avec une valeur égale à I dans le tableau Arr à tri. Ensuite, selon le Array Count_Arr, les éléments dans ARR sont disposés à la position correcte.
Il est divisé en quatre étapes:
1. Trouvez les plus grands et les plus petits éléments du tableau
2. Statistiques Le nombre de fois chaque élément avec une valeur de i apparaît dans le tableau, et enregistrez le i-ème élément du tableau Count_Ar
3. Accumuler tous les comptes (à partir du premier élément de Count_Ar, chaque élément et l'élément précédent sont ajoutés)
4. Traverser réversé le tableau d'origine: Placez chaque élément I dans l'élément COUNT_ARR (I) du nouveau tableau et soustrayez le count_arr (i) par 1 pour chaque élément.
Exemple:
La copie de code est la suivante:
/ **
* Count Le tri est un algorithme de tri non basé sur une comparaison.
* Cet algorithme a été proposé par Harold H. Seward en 1954.
* Son avantage est que lors du tri des entiers dans une certaine plage,
* Sa complexité est de (n + k) (où k est la gamme des entiers),
* Plus rapide que n'importe quel algorithme de tri de comparaison.
*
* /
Fonction Countsort (Arr, Min, Max) {
var i, z = 0, count = [];
pour (i = min; i <= max; i ++) {
compter [i] = 0;
}
for (i = 0; i <arr.length; i ++) {
compter [arr [i]] ++;
}
pour (i = min; i <= max; i ++) {
while (compter [i] -> 0) {
arr [z ++] = i;
}
}
retour arr;
}
// test
var i, arr = [];
pour (i = 0; i <100; i ++) {
arr.push (math.floor (math.random () * (141)));
}
Countort (arr, 0, 140);