Wie schreibt man Radixsort in Python?

Radixsort ist ein nicht vergleichender Sortieralgorithmus, der die Ziffern der Zahlen von der niedrigsten zur höchsten Stelle sortiert. Hier ist ein einfaches Beispiel, wie man Radixsort in Python implementieren kann:

```python
def counting_sort(arr, exp):
n = len(arr)
output = [0] * n
count [0] * 10

# Zähle die Vorkommen der Ziffern
for i in range(n):
index = (arr[i] // exp) % 10
count[index] += 1

# Ändere count[i] so, dass es die tatsächlichen Positionen enthält
for i in range(1, 10):
count[i] += count[i - 1]

# Baue das Ausgabearray auf
for i in range(n - 1, -1, -1):
index = (arr[i] // exp) % 10
output[count[index] - 1] = arr[i]
count[index] -= 1

# Kopiere das Ausgabearray zurück in arr
for i in range(n):
arr[i] = output[i]

def radix_sort(arr):
# Finde die maximale Zahl
max1 = max(arr)

# Wende counting_sort für jede Ziffer an
exp = 1
while max1 // exp > 0:
counting_sort(arr, exp)
exp *= 10

# Beispielverwendung
arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print("Sortiertes Array:", arr)
```

In diesem Code wird zuerst eine Hilfsfunktion `counting_sort` definiert, die für eine bestimmte Ziffer (bestimmt durch `exp`) die Ziffern zählt und das Array sortiert. Die Hauptfunktion `radix_sort` findet die maximale Zahl im Array und wendet dann `counting_sort` für jede Ziffer an, beginnend mit der niedrigsten.