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

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

Le tri Radix est un algorithme de tri selon le nombre de chiffres. Il compare et trie les éléments à trier en fonction du nombre sur chaque chiffre. Dans cet article, nous apprendrons comment implémenter l'algorithme de tri par base à l'aide de Python et fournirons des exemples de code détaillés.

Les étapes de mise en œuvre de l'algorithme sont les suivantes :

Étape 1 : Trouver la valeur maximale parmi les nombres à trier et déterminer le nombre de chiffres dans la valeur maximale.

Étape 2 : utilisez le tri par comptage pour trier chaque chiffre en fonction du chiffre de la valeur maximale.

Étape 3 : Répétez l'étape 2 jusqu'à ce que tous les chiffres aient été pris en compte.

Étape 4 : Affichez les résultats triés.

Ce qui suit est un exemple de code Python de l'algorithme de tri par base :

# 定义计数排序的方法
def countSort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    # 统计每个桶中元素的个数
    for i in range(n):
        index = arr[i] // exp
        count[index%10] += 1

    # 更新每个桶的位置
    for i in range(1, 10):
        count[i] += count[i-1]

    # 构建排序后的数组
    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index%10] - 1] = arr[i]
        count[index%10] -= 1
        i -= 1

    # 将排序后的数组更新给原数组
    for i in range(n):
        arr[i] = output[i]


# 定义基数排序的方法
def radixSort(arr):
    # 找到待排序数组的最大值
    maxval = max(arr)

    # 根据最大值的位数进行排序
    exp = 1
    while maxval // exp > 0:
        countSort(arr, exp)
        exp *= 10


# 主函数调用基数排序算法
if __name__ == "__main__":
    arr = [170, 45, 75, 90, 802, 24, 2, 66]
    radixSort(arr)
    print("排序后的数组：", arr)

Dans le code ci-dessus, nous définissons d'abord la méthode de tri par comptage countSort et utilisons le tri par comptage pour trier le tableau à trier en fonction du nombre de chiffres spécifié. . Ensuite, nous définissons la méthode de tri par base radixSort. Dans la méthode radixSort, nous trouvons la valeur maximale du tableau à trier, trions en fonction du nombre de chiffres dans la valeur maximale et appelons la méthode countSort pour trier chaque chiffre.

Dans la fonction principale, nous définissons un tableau arr à trier et appelons la méthode radixSort pour le tri. Enfin, nous générons le tableau trié.

Résumé :

Cet article présente comment utiliser Python pour implémenter l'algorithme de tri par base et fournit des exemples de code détaillés. J'espère qu'en lisant cet article, vous aurez une compréhension plus approfondie de la mise en œuvre de l'algorithme de tri par base.

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!