Tri par comptage en Python
Exemples Python3Le cœur du tri par comptage consiste à convertir les valeurs des données d'entrée en clés et à les stocker dans un espace de tableau supplémentaire. En tant que tri à complexité temporelle linéaire, le tri par comptage exige que les données d'entrée soient des entiers avec un intervalle défini.
Exemple
def countSort(arr):
output = [0 for i in range(256)]
count = [0 for i in range(256)]
ans = ["" for _ in arr]
for i in arr:
count[ord(i)] += 1
for i in range(256):
count[i] += count[i-1]
for i in range(len(arr)):
output[count[ord(arr[i])]-1] = arr[i]
count[ord(arr[i])] -= 1
for i in range(len(arr)):
ans[i] = output[i]
return ans
arr = "wwwexamplecom"
ans = countSort(arr)
print ( "Tableau de caractères trié : %s" %("".join(ans)) )
La sortie après exécution du code ci-dessus est :
符数组排序 bcmnoooruwwwAutres extensions