Ein Beispiel für die Verwendung von Python zur Implementierung der Prinzipien des Basissortierungsalgorithmus

Der Radix-Sortieralgorithmus ist eine Art Bucket-Sortieralgorithmus, der Werte basierend auf derselben Position in Gruppen sortiert. Vielleicht ist es etwas schwer zu verstehen. Schauen Sie sich das folgende Beispiel für das Prinzip des Basissortierungsalgorithmus an.

Prinzipielles Beispiel für einen Radix-Sortieralgorithmus

Geben Sie das Array [121.432.564,23,1,45.788] an und sortieren Sie das Array nach Radix, wie in der Abbildung gezeigt:

Sortieren Sie zuerst einstellige Werte, dann die Zehnerwerte sortieren und schließlich die Hunderterwerte sortieren. Die endgültige Ausgabe des sortierten Arrays ist [001.023.045.121.432.564.788]

Python-Code zur Implementierung des Basis-Sortieralgorithmus

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)

Das obige ist der detaillierte Inhalt vonEin Beispiel für die Verwendung von Python zur Implementierung der Prinzipien des Basissortierungsalgorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!