1 matplotlib绘制动画
matplotlib
是python中最经典的绘图包，里面
animation
模块能绘制动画。
首先导入小例子使用的模块：
from matplotlib import pyplot as plt
from matplotlib import animation
from random import randint, random
复制
生成数据，
frames_count
是帧的个数，
data_count
每个帧的柱子个数
class Data:
data_count = 32
frames_count = 2
def __init__(self, value):
self.value = value
self.color = (0.5, random(), random()) #rgb
# 造数据
@classmethod
def create(cls):
return [[Data(randint(1, cls.data_count)) for _ in range(cls.data_count)]
for frame_i in range(cls.frames_count)]
复制
绘制动画：
animation.FuncAnimation
函数的回调函数的参数
fi
表示第几帧，注意要调用
axs.cla()
清除上一帧。
def draw_chart():
fig = plt.figure(1, figsize=(16, 9))
axs = fig.add_subplot(111)
axs.set_xticks([])
axs.set_yticks([])
# 生成数据
frames = Data.create()
def animate(fi):
axs.cla() # clear last frame
axs.set_xticks([])
axs.set_yticks([])
return axs.bar(list(range(Data.data_count)), # X
[d.value for d in frames[fi]], # Y
1, # width
color=[d.color for d in frames[fi]] # color
)
# 动画展示
anim = animation.FuncAnimation(fig, animate, frames=len(frames))
plt.show()
draw_chart()
复制
2 排序算法的动画展示
学会第一部分如何制作动画后，可将此技术应用于排序算法调整过程的动态展示上。
首先生成测试使用的数据，待排序的数据个数至多
20个
，待排序序列为
random_wait_sort
，注意是随机序列。为每个值赋一个颜色值，这个由
random_rgb
负责：
data_count = 20 # here, max value of data_count is 20
random_wait_sort = [12, 34, 32, 24, 28, 39, 5,
22, 11, 25, 33, 32, 1, 25, 3, 8, 7, 1, 34, 7]
random_rgb = [(0.5, 0.811565104942967, 0.11211028937187217),
(0.5, 0.5201323831224014, 0.6660999602342474),
(0.5, 0.575976663060455, 0.17788242607567772),
(0.5, 0.6880174797416493, 0.43581701833249353),
(0.5, 0.4443131322001743, 0.6993600264279745),
(0.5, 0.5538835821863523, 0.889276053938713),
(0.5, 0.4851681185146841, 0.7977608586163772),
(0.5, 0.3886717808488436, 0.09319137949618972),
(0.5, 0.8952456581687489, 0.8282376936934484),
(0.5, 0.16360202854998007, 0.4538892160157194),
(0.5, 0.23233400128809478, 0.8544141586189615),
(0.5, 0.5224648797546528, 0.8194014475829123),
(0.5, 0.49396099968405016, 0.47441724394796825),
(0.5, 0.12078104526714728, 0.7715022079860492),
(0.5, 0.19428498518228154, 0.08174917157481443),
(0.5, 0.6058698403873457, 0.6085936584142663),
(0.5, 0.7801178568951216, 0.6414767240649862),
(0.5, 0.4768865661174162, 0.3889866229610085),
(0.5, 0.4301945092238082, 0.961688141676841),
(0.5, 0.40496648895289855, 0.24234095882836093)]
复制
再封装一个简单的数据对象
Data
：
class Data:
def __init__(self, value, rgb):
self.value = value
self.color = rgb
# 造数据
@classmethod
def create(cls):
return [Data(val, rgb) for val, rgb in zip(random_wait_sort[:data_count],
random_rgb[:data_count])]
复制
3 先拿冒泡实验
一旦发生调整，我们立即保存到帧列表
frames
中，注意此处需要
deepcopy
:
# 冒泡排序
def bubble_sort(waiting_sort_data):
frames = [waiting_sort_data]
ds = copy.deepcopy(waiting_sort_data)
for i in range(data_count-1):
for j in range(data_count-i-1):
if ds[j].value > ds[j+1].value:
ds[j], ds[j+1] = ds[j+1], ds[j]
frames.append(copy.deepcopy(ds))
frames.append(ds)
return frames
复制
实验结果一共得到
150
帧数据，其前
50
帧：
完整动画演示：
4 快速排序
先上代码，比较经典，值得回味：
def quick_sort(data_set):
frames = [data_set]
ds = copy.deepcopy(data_set)
def qsort(head, tail):
if tail - head > 1:
i = head
j = tail - 1
pivot = ds[j].value
while i < j:
if ds[i].value > pivot or ds[j].value < pivot:
ds[i], ds[j] = ds[j], ds[i]
frames.append(copy.deepcopy(ds))
if ds[i].value == pivot:
j -= 1
else:
i += 1
qsort(head, i)
qsort(i+1, tail)
qsort(0, data_count)
frames.append(ds)
return frames
复制
快速排序算法对输入为随机的序列优势往往较为明显，同样的输入数据，它只需要
24
帧就能完成排序：
5 选择排序
选择排序和堆排序都是选择思维，但是性能却不如堆排序：
def selection_sort(data_set):
frames = [data_set]
ds = copy.deepcopy(data_set)
for i in range(0, data_count-1):
for j in range(i+1, data_count):
if ds[j].value < ds[i].value:
ds[i], ds[j] = ds[j], ds[i]
frames.append(copy.deepcopy(ds))
frames.append(ds)
return frames
复制
同样的输入数据，它完成排序需要
108
帧:
动画展示如下，每轮会从未排序的列表中，挑出一个最小值，放到已排序序列后面。
6 堆排序
堆排序大大改进了选择排序，逻辑上使用二叉树，先建立一个大根堆，然后根节点与未排序序列的最后一个元素交换，重新对未排序序列建堆。
完整代码如下：
def heap_sort(data_set):
frames = [data_set]
ds = copy.deepcopy(data_set)
def heap_adjust(head, tail):
i = head * 2 + 1 # head的左孩子
while i < tail:
if i + 1 < tail and ds[i].value < ds[i+1].value: # 选择一个更大的孩子
i += 1
if ds[i].value <= ds[head].value:
break
ds[head], ds[i] = ds[i], ds[head]
frames.append(copy.deepcopy(ds))
head = i
i = i * 2 + 1
# 建立一个最大堆，从最后一个父节点开始调整
for i in range(data_count//2-1, -1, -1):
heap_adjust(i, data_count)
for i in range(data_count-1, 0, -1):
ds[i], ds[0] = ds[0], ds[i] # 把最大值放在位置i处
heap_adjust(0, i) # 从0~i-1进行堆调整
frames.append(ds)
return frames
复制
堆排序的性能也比较优秀，完成排序需要51次调整：
7 综合
依次调用以上常见的4种排序算法，分别保存所有帧和html文件。
waiting_sort_data = Data.create()
for sort_method in [bubble_sort, quick_sort, selection_sort, heap_sort]:
frames = sort_method(waiting_sort_data)
draw_chart(frames, file_name='%s.html' % (sort_method.__name__,))
复制
获取以上完整代码、所有数据文件、结果文件的方法：
- 关于下方公众号
- 回复：
sort