Bagaimana untuk melaksanakan algoritma jenis radix menggunakan Python?

Bagaimana untuk menggunakan Python untuk melaksanakan algoritma isihan radix?

Radix sorting ialah algoritma untuk mengisih mengikut bilangan digit. Ia membandingkan dan mengisih elemen yang hendak diisih mengikut nombor pada setiap digit. Dalam artikel ini, kita akan belajar cara melaksanakan algoritma isihan radix menggunakan Python dengan contoh kod terperinci.

Langkah pelaksanaan algoritma adalah seperti berikut:

Langkah 1: Cari nilai maksimum antara nombor yang hendak diisih, dan tentukan bilangan digit dalam nilai maksimum.

Langkah 2: Gunakan pengisihan mengira untuk mengisih setiap digit berdasarkan bilangan digit dalam nilai maksimum.

Langkah 3: Ulang langkah 2 sehingga semua digit telah dipertimbangkan.

Langkah 4: Keluarkan hasil yang diisih.

Berikut ialah contoh kod Python bagi algoritma isihan radix:

# 定义计数排序的方法
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)

Dalam kod di atas, kami mula-mula mentakrifkan kaedah isihan kira countSort, dan gunakan isihan kiraan untuk mengisih tatasusunan yang hendak diisih Isih mengikut bilangan digit yang ditentukan. Kemudian, kita mentakrifkan kaedah isihan radix radixSort Dalam kaedah radixSort, kita dapati nilai maksimum tatasusunan untuk diisih, mengisih mengikut bilangan digit dalam nilai maksimum, dan memanggil kaedah countSort untuk mengisih setiap digit.

Dalam fungsi utama, kami mentakrifkan arr tatasusunan untuk diisih dan memanggil kaedah radixSort untuk mengisih. Akhirnya, kami mengeluarkan tatasusunan yang diisih.

Ringkasan:

Artikel ini memperkenalkan cara menggunakan Python untuk melaksanakan algoritma isihan radix dan menyediakan contoh kod terperinci. Saya berharap dengan membaca artikel ini, anda akan mendapat pemahaman yang lebih mendalam tentang pelaksanaan algoritma isihan radix.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma jenis radix menggunakan Python?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!