Aqui está um algoritmo de classificação a ser usado para uma matriz de números inteiros ou estruturas que são codificadas por um número inteiro. Particularmente útil quando o intervalo de números inteiros está na ordem do tamanho da entrada.

A ideia principal é determinar a frequência de ocorrência dos inteiros e usar isso para determinar a ordem de classificação.

Um exemplo: digamos que obtemos o array {1,3,1,2}.

Primeiro determine o intervalo dos números inteiros, máximo e mínimo, 1 e 3 para esta entrada.

Em seguida, crie um array, chame-o de array de contagens, que é o tamanho do intervalo de inteiros 1, ou seja, 3 (3-1 1) neste caso.
Itere sobre a matriz de entrada, incrementando a entrada apropriada em contagens. A contagem de um determinado valor de entrada será colocada em contagens[valor - min]. Para a entrada fornecida, counts[0] manterá a contagem para o valor 1.

Isso resulta na matriz de contagens: {2,1,1}

Agora determine as contagens cumulativas, que são essencialmente contagens[i] = contagens[i-1] contagens[i].

Isso resulta na matriz de contagens cumulativas: {2,3,4}

Crie uma matriz de saída para a entrada classificada.

Agora, itere sobre a entrada na ordem inversa.

Em cada etapa, recupere a contagem cumulativa do valor na matriz de entrada. O valor será colocado no índice da matriz de saída correspondente à contagem recuperada - 1. Em seguida, diminua o valor da contagem cumulativa.

Na primeira etapa, o valor 2 é recuperado e uma contagem cumulativa de 3. O valor deve ser colocado no índice 2 (3-1) na saída.

Na próxima iteração, o valor 1 e a contagem cumulativa 2; então este '1' é colocado no índice 1 (2-1) da saída.

Continuando, o valor 3 e a contagem cumulativa 4; colocando-o no índice 3 da saída.

Finalmente, o valor 1 pela segunda vez e uma contagem cumulativa de 1 (já que a contagem foi decrementada na primeira vez que foi vista); então este '1' é colocado no índice 0 da saída.

, Veja como a iteração reversa preserva a ordem dos elementos iguais, tornando a classificação 'estável'

A matriz classificada resultante é {1,1,2,3}

func CountingSort(in []int) []int {
    // find the min/max values
    min := slices.Min(in)
    max := slices.Max(in)
    // create the count array
    counts := make([]int, max-min 1)
    for _, v := range in {
        counts[v-min]  
    }
    // determine cumulative counts
    for i := 1; i 



Pode ser mais eficiente? Deixe seus comentários e sugestões abaixo.

Obrigado!

O código desta postagem e de todas as postagens desta série pode ser encontrado aqui