python写的归并排序动态演示程序

使用 Matplotlib 进行归并排序动态演示的代码

python写的归并排序动态演示程序

下面是使用 Matplotlib 进行归并排序动态演示的代码。和之前的示例类似，我们定义了一个名为 merge_sort_animation 的递归函数来展示归并排序的排序过程。

在这个函数中，我们首先将数组划分为左右两个子数组，然后递归地对左右子数组进行归并排序。在进行归并操作时，我们使用两个指针 i 和 j 分别指向左右子数组的起始位置，并将较小的元素依次放入临时数组中。在归并完成后，我们将临时数组中的元素复制回原数组中相应的位置。

在动态演示过程中，我们使用 Matplotlib 中的 bar 函数绘制柱状图，用不同的颜色表示当前比较的两个元素，用文字显示元素的值。为了增加可读性，我们还在柱状图的顶部显示了当前递归层次以及左右子数组的范围。

接下来是归并排序算法的具体实现，同样是一个递归函数 merge_sort_animation，它会将数组递归分割成两个子数组，然后对这两个子数组进行归并操作，最后返回排序后的数组。在递归过程中，我们会通过 Matplotlib 的动画功能展示归并排序的排序过程：

最后，我们在主函数中生成随机数组，调用递归函数 merge_sort_animation 对数组进行归并排序并展示排序过程：

import matplotlib.pyplot as plt
import random

def merge_sort_animation(data, start, end, fig, ax, depth):
    if end - start <= 1:
        return

    mid = (start + end) // 2
    merge_sort_animation(data, start, mid, fig, ax, depth+1)
    merge_sort_animation(data, mid, end, fig, ax, depth+1)

    temp = []
    i, j = start, mid
    while i < mid and j < end:
        if data[i] < data[j]:
            temp.append(data[i])
            i += 1
        else:
            temp.append(data[j])
            j += 1

        # update the bar chart
        color = ['b'] * len(data)
        color[i:j] = ['r'] * (j-i)
        ax.clear()
        ax.bar(range(len(data)), data, color=color)
        ax.set_xlim(0, len(data))
        ax.set_ylim(0, max(data) + 10)
        plt.title(f'Merge Sort (Depth={depth}, Range=[{start},{end}))')
        for k in range(len(data)):
            plt.text(k, data[k] + 1, data[k], horizontalalignment='center', fontweight='bold', color='black')
        plt.text(mid-1, max(data) + 5, '|', horizontalalignment='center', fontweight='bold', color='black')
        plt.pause(0.1)

    while i < mid:
        temp.append(data[i])
        i += 1

        # update the bar chart
        color = ['b'] * len(data)
        color[start:i] = ['r'] * (i-start)
        ax.clear()
        ax.bar(range(len(data)), data, color=color)
        ax.set_xlim(0, len(data))
        ax.set_ylim(0, max(data) + 10)
        plt.title(f'Merge Sort (Depth={depth}, Range=[{start},{end}))')
        for k in range(len(data)):
            plt.text(k, data[k] + 1, data[k], horizontalalignment='center', fontweight='bold', color='black')
        plt.text(mid-1, max(data) + 5, '|', horizontalalignment='center', fontweight='bold', color='black')
def merge_sort_animation(data, left, right, ax):
    if left >= right:
        return

    mid = (left + right) // 2

    merge_sort_animation(data, left, mid, ax)
    merge_sort_animation(data, mid+1, right, ax)

    # Merge
    temp = []
    i = left
    j = mid+1
    while i <= mid and j <= right:
        if data[i] < data[j]:
            temp.append(data[i])
            i += 1
        else:
            temp.append(data[j])
            j += 1

    while i <= mid:
        temp.append(data[i])
        i += 1

    while j <= right:
        temp.append(data[j])
        j += 1

    data[left:right+1] = temp

    # Update the bar chart
    ax.clear()
    color = ['b'] * len(data)
    for k in range(left, right+1):
        color[k] = 'g'
    ax.bar(range(len(data)), data, color=color)
    ax.set_xlim(0, len(data))
    ax.set_ylim(0, max(data) + 10)
    plt.title('Merge Sort')
    for k in range(len(data)):
        plt.text(k, data[k] + 1, data[k], horizontalalignment='center', fontweight='bold', color='black')
    plt.pause(1)
if __name__ == '__main__':
    # Generate random data
    data = [random.randint(0, 100) for _ in range(10)]
    print('Unsorted data:', data)

    # Show the sorting process
    fig, ax = plt.subplots()
    ax.bar(range(len(data)), data)
    ax.set_xlim(0, len(data))
    ax.set_ylim(0, max(data) + 10)
    plt.title('Merge Sort')
    plt.show(block=False)

    merge_sort_animation(data, 0, len(data)-1, ax)

    plt.show()

    # Sort the data using merge sort
    merge_sort(data)

    print('Sorted data:', data)

这样就完成了归并排序算法的动态演示，我们可以通过观察 Matplotlib 绘制的柱状图来了解归并排序的具体过程。