Un exemple d'utilisation de Python pour implémenter les principes de l'algorithme de tri radix

L'algorithme de tri par base est un type d'algorithme de tri par compartiment, qui trie les valeurs en fonction de la même position en groupes. C'est peut-être un peu difficile à comprendre. Vous pouvez regarder l'exemple suivant du principe de l'algorithme de tri par base.

Exemple de principe d'algorithme de tri par base

Spécifiez le tableau [121,432,564,23,1,45,788] et triez le tableau par base, comme indiqué dans la figure :

Triez d'abord le valeurs à un chiffre, puis trier les valeurs à plusieurs dizaines, et enfin trier les valeurs à centaines de chiffres. La sortie finale du tableau trié est [001,023,045,121,432,564,788]

Code Python pour implémenter l'algorithme de tri de base

def countingSort(array, place):
    size = len(array)
    output = [0] * size
    count = [0] * 10

    for i in range(0, size):
        index = array[i] // place
        count[index % 10] += 1

 
    for i in range(1, 10):
        count[i] += count[i - 1]

    i = size - 1
    while i >= 0:
        index = array[i] // place
        output[count[index % 10] - 1] = array[i]
        count[index % 10] -= 1
        i -= 1

    for i in range(0, size):
        array[i] = output[i]

def radixSort(array):
    # Get maximum element
    max_element = max(array)

    place = 1
    while max_element // place > 0:
        countingSort(array, place)
        place *= 10

data = [121, 432, 564, 23, 1, 45, 788]
radixSort(data)
print(data)

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!