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