How to implement radix sort algorithm using Python?

How to implement the radix sorting algorithm using Python?

Radix sorting is an algorithm for sorting according to the number of digits. It compares and sorts the elements to be sorted according to the number on each digit. In this article, we will learn how to implement the radix sort algorithm using Python and provide detailed code examples.

The algorithm implementation steps are as follows:

Step 1: Find the maximum value among the numbers to be sorted, and determine the number of digits in the maximum value.

Step 2: Use counting sort to sort each digit according to the number of digits in the maximum value.

Step 3: Repeat step 2 until all digits have been considered.

Step 4: Output the sorted results.

The following is a Python code example of the radix sorting algorithm:

# 定义计数排序的方法
def countSort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    # 统计每个桶中元素的个数
    for i in range(n):
        index = arr[i] // exp
        count[index%10] += 1

    # 更新每个桶的位置
    for i in range(1, 10):
        count[i] += count[i-1]

    # 构建排序后的数组
    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index%10] - 1] = arr[i]
        count[index%10] -= 1
        i -= 1

    # 将排序后的数组更新给原数组
    for i in range(n):
        arr[i] = output[i]


# 定义基数排序的方法
def radixSort(arr):
    # 找到待排序数组的最大值
    maxval = max(arr)

    # 根据最大值的位数进行排序
    exp = 1
    while maxval // exp > 0:
        countSort(arr, exp)
        exp *= 10


# 主函数调用基数排序算法
if __name__ == "__main__":
    arr = [170, 45, 75, 90, 802, 24, 2, 66]
    radixSort(arr)
    print("排序后的数组：", arr)

In the above code, we first define the counting sorting method countSort, and use counting sorting to sort the array according to the specified number of digits. Sort. Then, we define the radix sort method radixSort. In the radixSort method, we find the maximum value of the array to be sorted, sort according to the number of digits in the maximum value, and call the countSort method to sort each digit.

In the main function, we define an array arr to be sorted and call the radixSort method for sorting. Finally, we output the sorted array.

Summary:

This article introduces how to use Python to implement the radix sorting algorithm and provides detailed code examples. I hope that by reading this article, you will have a deeper understanding of the implementation of the radix sort algorithm.

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