matplotlib应用之排序算法动画模拟-轻识

说在前面

Python扩展库matplotlib，可以绘制多种形式的图形，例如折线图、散点图、饼图、柱状图等等，一般来说学会生成静态的图像就可以了，但这显然不够有趣。

我们可以使用循环结构输出多张图像，每张图像x、y轴上的数据可以发生变化，通过暂停一小段时间后更新图像的方法来实现动画的效果。

今天我先来做一个使用matplotlib绘图模拟排序过程的小程序，抛砖引玉，希望能够对大家有所启发，期待您开发出更有趣、有用的程序。

一、冒泡排序经典算法

首先我们来回顾冒泡排序的经典算法：

import numpy as npn = 10y = np.random.randint(1, 19, size=n) for i in range(n-1, 0, -1):    for j in range(i):        if y[j] > y[j+1]:            y[j], y[j+1] = y[j+1], y[j]print(y)

然后我们学会输出某个时刻柱形图的方法：

import matplotlib.pyplot as pltimport numpy as np#显示当前柱状图def show_bar(x, y, cs, time):    plt.cla()                 #清除当前轴域    plt.title("冒泡排序动画") #显示标题    plt.xticks(x)             #显示x轴刻度（元素下标）    plt.xlabel("元素下标")    #显示x轴标签    plt.ylabel("元素值")      #显示y轴标签    plt.bar(x, y, color=cs)   #显示柱状图    plt.pause(time)           #图像暂停，以实现动画效果plt.rcParams['font.sans-serif']=['SimHei'] # 解决中文乱码问题plt.rcParams['axes.unicode_minus'] = False # 解决坐标轴刻度负号乱码
n = 10x = np.arange(0, n, 1)y = np.random.randint(1, 19, size=n)cs = ['b'] * nshow_bar(x, y, cs, 2) #当前图像暂停2秒plt.show()

在该段程序中，我们先规定了x、y轴的数据，其中x轴的数据存储在数组x中，表示数组元素下标；y轴的数据存储在数组y中，表示数组元素的值；另外还设置了每个元素对应的柱形颜色，存储在数组cs中，一开始默认都是蓝色。

为了体现模块化编程思想，我们定义了一个函数show_bar(x, y, cs, time)，用来显示当前时刻的柱状图，其中time表示暂停时间，目的是让图像暂停，以实现动画效果。显示图片如下所示：

冒泡排序算法中外层循环变量i指向待排序数组的右边界，内层循环变量j作为游标从左向右依次扫描待排序数组。我们可以事先约定好各元素对应柱形的颜色：已排序元素为绿色、待排序元素为蓝色、游标j所指元素为黄色，为突出显示交换过程，我们设置被交换元素的柱形颜色为红色（显示很短的一段时间后，又恢复成蓝色）。

接下来需要思考的是何时修改相关柱形的颜色，并显示当时的柱状图，即在冒泡排序源代码的哪些位置插入修改颜色和显示柱状图的代码，才能较好地实现动画效果。

此处每个人的想法都不一样，方案肯定有很多。我的做法是：

1. 排序之前显示柱状图，并暂停2秒；

2. 每趟排序，移动游标之前先设置当前游标所指元素柱形为黄色，显示柱状图并暂停0.2秒，这样若无交换操作即可实现快速扫描动画；

3. 扫描过程中若需要发生交换操作，则设置交换柱形颜色分别为红色和黄色，显示柱状图并暂停0.4秒，这样可以突出交换过程；

4. 扫描过程中，每处理完当前元素，即还原其柱形为蓝色；

5. 每完成一趟排序，先让图像暂停0.5秒，再设置已排序元素柱形为绿色，显示柱状图并暂停1秒，以突出显示当前排序结果，优化动画效果；

6. 最后一个元素无需排序，设置其柱形为绿色，显示柱状图并暂停1秒，即完成动画演示。

完整源代码如下所示：

import matplotlib.pyplot as pltimport numpy as np
#显示当前柱状图def show_bar(x, y, cs, time):    plt.cla()                 #清除当前轴域    plt.title("冒泡排序动画") #显示标题    plt.xticks(x)             #显示x轴刻度（元素下标）    plt.xlabel("元素下标")    #显示x轴标签    plt.ylabel("元素值")      #显示y轴标签    plt.bar(x, y, color=cs)   #显示柱状图    plt.pause(time)           #图像暂停，以实现动画效果plt.rcParams['font.sans-serif']=['SimHei'] # 解决中文乱码问题plt.rcParams['axes.unicode_minus'] = False # 解决坐标轴刻度负号乱码
n = 10x = np.arange(0, n, 1)y = np.random.randint(1, 19, size=n)cs = ['b'] * nshow_bar(x, y, cs, 2) #当前图像暂停2秒
for i in range(n-1, 0, -1):    for j in range(i):        cs[j] = 'y'  #设置当前游标所指元素柱形为黄色        show_bar(x, y, cs, 0.2) #当前图像暂停0.2秒        if y[j] > y[j+1]:            y[j], y[j+1] = y[j+1], y[j]            cs[j], cs[j+1] = 'r', 'y' #设置交换柱形颜色            show_bar(x, y, cs, 0.4) #当前图像暂停0.4秒                    cs[j] = 'b' #还原当前元素柱形为蓝色    plt.pause(0.5)  #图像暂停，以实现动画效果    cs[i] = 'g'     #设置已排序元素柱形为绿色    show_bar(x, y, cs, 1) #当前图像暂停1秒
cs[0] = 'g' #最后一个元素无需排序，设置其柱形为绿色show_bar(x, y, cs, 1) #当前图像暂停1秒 plt.show()

二、选择排序经典算法

同理我们可以实现经典选择排序算法的动画演示，经典选择排序算法源代码如下：

n = 10y = np.random.randint(1, 19, size=n)for i in range(n-1):    k = i    for j in range(i+1, n):        if y[j] < y[k]:            k = j    if k != i:        y[k], y[i] = y[i], y[k]print(y)

绘图方法与前述冒泡排序中基本相同，数组x、y、cs和各柱形颜色的含义完全一致，绘图函数show_bar(x, y, cs, time)完全相同。区别仅在于选择排序中多了一个辅助变量k，用来指向待排序数组的最小元素，我们可以设置其柱形为红色，并在修改k值时，让图像暂停0.8秒。

完整源代码如下所示：

import matplotlib.pyplot as pltimport numpy as np
#显示当前柱状图def show_bar(x, y, cs, time):    plt.cla()                 #清除当前轴域    plt.title("选择排序动画") #显示标题    plt.xticks(x)             #显示x轴刻度（元素下标）    plt.xlabel("元素下标")    #显示x轴标签    plt.ylabel("元素值")      #显示y轴标签    plt.bar(x, y, color=cs)   #显示柱状图    plt.pause(time)           #图像暂停，以实现动画效果plt.rcParams['font.sans-serif']=['SimHei'] # 解决中文乱码问题plt.rcParams['axes.unicode_minus'] = False # 解决坐标轴刻度负号乱码
n = 10x = np.arange(0, n, 1)y = np.random.randint(1, 19, size=n)cs = ['b'] * n
show_bar(x, y, cs, 2) #当前图像暂停2秒for i in range(n-1):    k = i    for j in range(i+1, n):        cs[j] = 'y'  #设置当前游标所指元素柱形为黄色        cs[k] = 'r'  #设置当前最小值元素柱形为红色        show_bar(x, y, cs, 0.2) #当前图像暂停0.2秒        if y[j] < y[k]:            cs[k] = 'b'  #修改原最小值处元素柱形为蓝色            k = j            cs[k] = 'r'  #设置当前最小值元素柱形为红色            show_bar(x, y, cs, 0.8) #当前图像暂停0.8秒        else:            cs[j] = 'b'  #还原当前元素柱形为蓝色
    plt.pause(0.5)      #图像暂停，以实现动画效果    if k != i:        y[k], y[i] = y[i], y[k]        cs[k], cs[i] = 'b', 'r' #设置交换柱形颜色        show_bar(x, y, cs, 0.8) #当前图像暂停0.8秒            cs[i] = 'g'           #设置已排序元素柱形为绿色    show_bar(x, y, cs, 1) #当前图像暂停1秒
cs[n-1] = 'g' #最后一个元素无需排序，设置其柱形为绿色show_bar(x, y, cs, 1) #当前图像暂停1秒 plt.show()