Tri par comptage

Voici un algorithme de tri à utiliser pour un tableau d'entiers ou de structures dont la clé est un entier. Particulièrement utile lorsque la plage d'entiers est de l'ordre de la taille de l'entrée.

L'idée principale est de déterminer la fréquence d'apparition des entiers et de l'utiliser pour déterminer l'ordre de tri.

Un exemple : disons que nous obtenons le tableau {1,3,1,2}.

Déterminez d'abord la plage des nombres entiers, max et min, 1 et 3 pour cette entrée.

Créez ensuite un tableau, appelez-le le tableau des comptes, c'est-à-dire la taille de la plage entière+1, donc 3 (3-1+1) dans ce cas.
Parcourez le tableau d'entrée, en incrémentant l'entrée appropriée en nombre. Le nombre d'une valeur d'entrée donnée sera placé à counts[value - min]. Pour l'entrée donnée, counts[0] contiendra le décompte pour la valeur 1.

Cela donne le tableau de comptes : {2,1,1}

Déterminez maintenant les décomptes cumulés, qui sont essentiellement counts[i] = counts[i-1]+counts[i].

Cela donne le tableau des comptes cumulés : {2,3,4}

Créez un tableau de sortie pour l'entrée triée.

Maintenant, parcourez l'entrée dans l'ordre inverse.

À chaque étape, récupérez le nombre cumulé de la valeur dans le tableau d'entrée. La valeur sera placée à l'index du tableau de sortie correspondant au nombre récupéré - 1. Décrémentez ensuite la valeur du nombre cumulé.

Dans la première étape, la valeur 2 est récupérée et un décompte cumulé de 3. La valeur doit être placée à l'index 2 (3-1) dans la sortie.

Dans l'itération suivante, la valeur 1 et le nombre cumulé 2 ; donc ce '1' est placé à l'index 1 (2-1) de la sortie.

En continu, la valeur 3 et le compte cumulé 4 ; en le plaçant à l'index 3 de la sortie.

Enfin, la valeur 1 pour la deuxième fois et un décompte cumulé de 1 (puisque le décompte a été décrémenté la première fois qu'il a été vu) ; donc ce '1' est placé à l'index 0 de la sortie.

, voyez comment l'itération inverse préserve l'ordre des éléments égaux, rendant le tri "stable"

Le tableau trié résultant est {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 < len(counts); i++ {
        counts[i] = counts[i-1] + counts[i]
    }
    // create the output array
    out := make([]int, len(in))
    for i := range in {
        v := in[len(in)-1-i]
        out[counts[v-min]-1] = v
        counts[v-min]--
    }
    return out
}

Peut-il être rendu plus efficace ? Laissez vos commentaires et suggestions ci-dessous.

Merci !

Le code de cet article et de tous les articles de cette série peut être trouvé ici

以上是Tri par comptage的详细内容。更多信息请关注PHP中文网其他相关文章！