概述
近期在知乎上看到了几个排序算法可视化视频，顿时兴致盎然，也想自己实现一次。最后在Matplotlib库的帮助下达成了这个目的，做出了一条还算满意的视频，最后也开源了这个小玩具。
下面就是这个视频成品，用Matplotlib库自动生成原始素材，并用Premiere进行了后期处理。视频中把九种排序算法放在一起作为对比，分别是：
插入排序 希尔排序 选择排序
归并排序 快速排序 堆排序
冒泡排序 梳排序 猴子排序
先来一睹为快吧：
https://www.zhihu.com/video/991814541629505536
（加入猴子排序完全是想皮一下，毕竟一次成功的概率只有
）
在构思方案的时候，我不可避免的走了一条由弯到直的路。当时的初始方案是，用python模拟各种排序算法，然后逐帧生成步骤图片，将图片序列导入AE转成视频。后来觉得python直接写图片太麻烦，有没有更方便的轮子？于是想到了Matplotlib库可以绘制柱状图，刚好与我想要的图片形式重合。后来改成了用Python+Matplotlib逐帧生成图片，再将图片序列导入AE转成视频。最后，又觉得图片序列导入AE太麻烦，能不能直接输出视频？所幸Matplotlib既支持逐帧动画，又可以和FFMpeg结合，直接以mp4格式将动画输出。excited！
至于如何得到排序算法每个时刻的切片，我想过将帧编号和排序算法的进度联系起来，边播放边获取下一帧的数据。后来发现操作起来很有难度，完全可以先走一遍排序算法，得到所有帧的数据，再逐帧播放。这样虽然多耗了点内存，实现起来还是很简单的。下面以基本的选择排序为例介绍一下：
def selection_sort(data_set):
ds = copy.deepcopy(data_set)
for i in range(0, Data.data_count-1):
for j in range(i+1, Data.data_count):
if ds[j].value < ds[i].value:
ds[i], ds[j] = ds[j], ds[i]
return ds
选择排序的代码非常简单，我们要做的就是在算法比较有代表性的地方截取数据切片作为帧数据，然后同时处理帧数据，为某些重要的数值染色。最后的代码是这样的：
def selection_sort(data_set):
# FRAME OPERATION BEGIN
frames = [data_set]
# FRAME OPERATION END
ds = copy.deepcopy(data_set)
for i in range(0, Data.data_count-1):
for j in range(i+1, Data.data_count):
# FRAME OPERATION BEGIN
ds_r = copy.deepcopy(ds)
frames.append(ds_r)
ds_r[i].set_color('r')
ds_r[j].set_color('k')
# FRAME OPERATION END
if ds[j].value < ds[i].value:
ds[i], ds[j] = ds[j], ds[i]
# FRAME OPERATION BEGIN
frames.append(ds)
return frames
# FRAME OPERATION END
可以看到新代码在原先的代码上加了三块处理帧数据的操作，并用注释标了出来。第一块：初始化帧列表，原始数据作为第一帧；第二块：在第二层循环内部截取帧，并把第i个数据涂为红色（r），第j个数据涂为黑色（k）；第三块：在帧列表中加入已排序的数据作为最后一帧，并返回帧列表。
这样，我们就可以用最直观的方式看到选择排序的过程以及i和j的意义：第i个元素一直在取j扫过部分的最小值。
https://www.zhihu.com/video/991489563390488576
当然，这只是这些排序算法中较为简单的截取及染色方案。还有一些算法比较抽象，从排序过程中难以看出规律，比如堆排序。我给大根堆的每一层涂上了不同的颜色，并用红色表示正在下沉或上浮的结点，用黑色表示红色结点调整位置的过程中需要比较的孩子结点或父结点。这下排序过程总算直观了些：
https://www.zhihu.com/video/991489923932835840
至于Matplotlib的绘图和动画部分，可以查阅官网文档，这里就不再赘述了。但是把动画导出成mp4文件需要FFMpeg库的帮助，具体做法这篇文章讲得很好：matplotlib animation动画保存(save函数)详解。
我已经把这些代码全部开源，并优化了一下用户接口，有窗口播放动画（9个算法并列播放或单个算法播放）、生成mp4和html的功能，可以参考README文档使用。GitHub仓库地址：zamhown/sorting-visualizergithub.com
说来惭愧，这是我写README最认真的一次……欢迎star、fork或者提issue。如果想改进或者添加新的排序算法欢迎提交pr。祝端午玩得愉快~
最后
以上就是懵懂苗条为你收集整理的python 排序算法库_使用Python+Matplotlib库制作经典排序算法可视化动画的全部内容，希望文章能够帮你解决python 排序算法库_使用Python+Matplotlib库制作经典排序算法可视化动画所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复