An example of using Python to implement the principles of radix sorting algorithm

The radix sorting algorithm is a type of bucket sorting algorithm, which sorts values ​​based on the same position into groups. Maybe it's a bit hard to understand. You can look at the following example of the principle of radix sorting algorithm.

Principle example of radix sort algorithm

Specify the array [121,432,564,23,1,45,788], and sort the array by radix, as shown in the figure:

#First sort the single-digit values, then sort the tens-digit values, and finally sort the hundreds-digit values, and finally output the sorted The array is [001,023,045,121,432,564,788]

Python code to implement the radix sorting algorithm

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)

The above is the detailed content of An example of using Python to implement the principles of radix sorting algorithm. For more information, please follow other related articles on the PHP Chinese website!