Python排序算法可视化

前言

在为大一同学们写C语言期末复习指南时,在菜鸟教程上看到了几幅排序算法的散点动图,感觉很有意思,并且立即想到了之前参加焦糖招新的时候用过的matplotlib可视化库,尝试实现一下各种算法。


正文

话不多说,立即开始尝试:

准备工作

简单想了一下,在matplotlib库提供的几种不同的图形中,散点图可能会最为直观,翻阅doc可以找到相关的函数:

matplotlib.pyplot.scatter(x, y, s=None, c=None, marker=None, cmap=None, norm=None, vmin=None, vmax=None, alpha=None, linewidths=None, verts=<deprecated parameter>, edgecolors=None, *, plotnonfinite=False, data=None, **kwargs)

参数说明:

更多的参数项似乎很难用得到,于是这里就不写了。

思路确立

第一次建立的初期思路如下:

冒泡排序
快速排序
...
pyplot.scatter(x,y,s)
matplotlib.animation.FuncAnimation
生成一个随机的数字列表
构建排序算法
在排序过程中得到每一帧的散点状态
逐帧绘制并合成
得到连续画面

看起来一切进展还算顺利,然而到了逐帧绘制合成时,问题出现了。

我们回头看看FuncAnimation函数的参数说明:

class matplotlib.animation.FuncAnimation(fig, func, frames=None, init_func=None, fargs=None, save_count=None, *, cache_frame_data=True, **kwargs)

fig是要选取的图变量,func是每一帧的更新函数

FuncAnimation调用func来绘制每一帧画面,可我们的排序算法是一个循环的过程,我们需要展示的是每次循环的结果,也就是我们绘制每一帧的过程是在排序过程中发生的,FuncAnimation无法直接穿透循环过程来得到每一帧的数据,用这种方法来更新每一帧将遇到巨大的困难。

那么如何解决这个问题呢?

两个思路:

第一个思路乍看起来还不错,但如果数据量较大,将占用大量的内存来存储数据。

所以我决定使用第二个思路,自己绘制每一帧的画面。

修改后的思路为:

pyplot.scatter(x,y,s,c)
生成连续随机数列表
构建排序算法
在排序过程中绘制散点图
直接得到动画

按照这个思路,我们从头开始构建:

生成连续随机数列表

这里直接生成了一组0~99的数据,为了保证排序结束的散点图是一条直线,要避免生成重复的随机数,所以调用random.sample

构建排序算法

冒泡排序
插入排序
希尔排序(升级版插入排序)
快速排序

绘制的逻辑

要做到自己绘制每一帧,我们需要按照这样的逻辑来执行:

排序过程
plt.cla()
plt.scatter(x,y,s,c)
进入新的周期
排序结束后
擦除上一帧的画面
暂停一个时长
绘制当前的散点
plt.show()
plt.close()

那么代码就很简单了:

将这段代码放置到能体现排序算法特点的循环周期内,在循环结束依次后展示所有的画面:

至此,可视化过程就已经实现了。


 

后记

完整代码示例

更加简洁和有效的代码,直接将gif保存到本地:

shellSort

insertSort

bubbleSort

quickSort

简单修改一下图形绘制模式,把散点图修改为柱状图,可以很容易得到柱状图形式的排序动画:

效果如图:

bubbleSort

quickSort

shellSort

insertSort