python写的基数排序动态演示程序

python写的基数排序动态演示程序

以下是一个使用 Matplotlib 进行基数排序动态演示的代码，其中在柱形图中区分正在排序的数字：

import matplotlib.pyplot as plt
import numpy as np
import time

def radix_sort(arr, ax):
    # 获取数组的最大值
    max_value = max(arr)

    # 计算最大值的位数
    num_digits = len(str(max_value))

    # 初始化桶
    buckets = [[] for i in range(10)]

    # 按照位数进行排序
    for i in range(num_digits):
        # 将元素放入桶中
        for j in arr:
            digit = (j // 10**i) % 10
            buckets[digit].append(j)

        # 更新柱状图并暂停一段时间
        ax.clear()
        for k, bucket in enumerate(buckets):
            for l, num in enumerate(bucket):
                color = 'red' if (num // 10**i) % 10 == k else 'gray'
                ax.bar(len(arr)*k + l, num, color=color)
                ax.text(len(arr)*k + l, num + 1, str(num), horizontalalignment='center')
        plt.pause(0.5)

        # 从桶中取出元素
        arr = []
        for bucket in buckets:
            arr.extend(bucket)
            bucket.clear()

    return arr

# 生成随机数组
arr = np.random.randint(1, 100, 50)

# 创建画布和轴对象
fig, ax = plt.subplots()
ax.set_title("Radix Sort")

# 绘制初始柱状图
ax.bar(range(len(arr)), arr)
for j, num in enumerate(arr):
    ax.text(j, num + 1, str(num), horizontalalignment='center')

# 刷新画布，暂停一段时间，然后开始基数排序
fig.canvas.draw()
plt.pause(1)

sorted_arr = radix_sort(arr, ax)

# 更新柱状图并显示
ax.bar(range(len(sorted_arr)), sorted_arr)
for j, num in enumerate(sorted_arr):
    ax.text(j, num + 1, str(num), horizontalalignment='center')
fig.canvas.draw()
plt.show()

在此代码中，我们创建了 10 个桶，并将元素按照位数放入这些桶中。在更新柱状图时，我们使用红色标记当前正在排序的数字，使用灰色标记其他数字。为了能够正确显示所有数字，我们需要使用 len(arr)*k + l 计算每个数字的位置，其中 k 表示桶的索引，l 表示桶中元素的索引。每次将所有数字放入桶中后，我们暂停一段时间并更新柱状图，以显示当前排序的进度。完成基数排序后，我们将更新柱状图以显示排序后的结果，并显示最终的柱状图。