A Counting Sort é um algoritmo de classificação estável. A Count Strating usa uma matriz adicional count_arr, onde o i-ésimo elemento é o número de elementos com um valor igual a I na Array ARR para ser classificado. Então, de acordo com a matriz count_arr, os elementos do ARR são organizados para a posição correta.
É dividido em quatro etapas:
1. Encontre os elementos maiores e menores da matriz a ser classificada
2. Estatísticas O número de vezes cada elemento com um valor de I aparece na matriz e salve o I-és
3. Acumule todas as contagens (começando pelo primeiro elemento em Count_arr, cada item e o item anterior são adicionados)
4. Travesse a matriz original: coloque cada elemento i no item Count_arr (i) da nova matriz e subtraia o count_arr (i) por 1 para cada elemento.
Exemplo:
A cópia do código é a seguinte:
/**
* Counting Counting é um algoritmo de classificação não baseado em comparação.
* Este algoritmo foi proposto por Harold H. Seward em 1954.
* Sua vantagem é que, ao classificar números inteiros dentro de um determinado intervalo,
* Sua complexidade é (n+k) (onde k é a gama de números inteiros),
* Mais rápido do que qualquer algoritmo de classificação de comparação.
*
*/
função countSort (arr, min, max) {
var i, z = 0, count = [];
para (i = min; i <= max; i ++) {
contagem [i] = 0;
}
for (i = 0; i <arn.length; i ++) {
Conte [arr [i]] ++;
}
para (i = min; i <= max; i ++) {
while (contagem [i]-> 0) {
arr [z ++] = i;
}
}
retornar arr;
}
// teste
var i, arr = [];
for (i = 0; i <100; i ++) {
ar.push (math.floor (math.random () * (141)));
}
CountSort (arr, 0, 140);