Comment implémenter un algorithme de tri par comptage en utilisant Python ?

Comment implémenter un algorithme de tri par comptage en utilisant Python ?

Le tri par comptage est un algorithme de tri linéaire à complexité temporelle qui peut être utilisé pour trier des entiers ou des tableaux avec une certaine plage de valeurs. Son idée de base est de compter le nombre de fois où chaque élément apparaît et de placer l'élément dans la bonne position en fonction du nombre de fois. Ce qui suit présentera comment utiliser Python pour implémenter l'algorithme de tri par comptage et donnera des exemples de code spécifiques.

Tout d'abord, nous devons clarifier l'idée centrale du tri par comptage. Les étapes d'exécution du tri par comptage sont les suivantes :

1. Trouvez le plus grand nombre dans le tableau à trier et créez un nombre de tableau auxiliaire avec une longueur égale au nombre maximum plus 1, qui est utilisé pour stocker le nombre d'occurrences de chaque élément ;
2. Parcourez le tableau à trier, comptez le nombre d'occurrences de chaque élément et stockez-le dans le tableau count ;
3. Effectuez une opération d'accumulation sur le tableau count pour obtenir l'indice de position correct de chaque élément ; Créez un tableau de résultats de la même longueur que le tableau à trier ;
4. Parcourez le tableau à trier et placez les éléments à la bonne position en fonction de l'index de la valeur de l'élément dans le tableau de comptage ;
5. Renvoyez le résultat ; résultat du tableau, qui est le tableau trié.
6. Ce qui suit est un exemple de code utilisant Python pour implémenter l'algorithme de tri par comptage :

def counting_sort(arr):
    # 找出最大值
    max_val = max(arr)
    # 创建辅助数组count，并初始化为0
    count = [0] * (max_val + 1)

    # 统计每个元素出现的次数
    for num in arr:
        count[num] += 1

    # 对count数组进行累加操作
    for i in range(1, len(count)):
        count[i] += count[i - 1]

    # 创建结果数组result
    result = [0] * len(arr)

    # 将元素放置到正确的位置上
    for num in arr:
        index = count[num] - 1
        result[index] = num
        count[num] -= 1

    # 返回结果数组
    return result

Ensuite, nous pouvons tester l'algorithme de tri par comptage de la manière suivante :

arr = [4, 2, 3, 4, 1]
sorted_arr = counting_sort(arr)
print(sorted_arr)

Exécutez le code ci-dessus, le résultat de sortie est : [1 , 2, 3, 4, 4].

Grâce aux exemples de code ci-dessus, nous pouvons voir que les étapes de mise en œuvre de l'algorithme de tri par comptage sont relativement simples. Il s'agit d'un algorithme de tri très efficace pour les tableaux avec une certaine plage de valeurs. J'espère que cet article vous aidera à comprendre et à utiliser l'algorithme de tri par comptage !

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!