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)

参数说明:

  • image-20201224150426475

    必需参数,确定散点的横纵坐标,支持传入array(也就是说可以传入两个列表来直接画出所有的点)

  • s: float or array-like,shapr(n,),optinal

    可选项,控制各个散点的大小

  • c: array-like or list of colors or color, optional

    可选项,控制散点颜色

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

思路确立

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

graph TB
生成一个随机的数字列表-->构建排序算法--"冒泡排序<br>快速排序<br>..."-->在排序过程中得到每一帧的散点状态--"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无法直接穿透循环过程来得到每一帧的数据,用这种方法来更新每一帧将遇到巨大的困难。

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

两个思路:

  • 1.将循环过程中每一帧的数据保存在列表中,在最后调用func的时候来遍历数组绘图
  • 2.抛弃FuncAnimation函数,自己逐帧绘制

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

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

修改后的思路为:

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

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

生成连续随机数列表

import random
a = list(range(100))
a = random.sample(a,k = 100)

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

构建排序算法

冒泡排序
def bubbleSort(a):
for i in range(len(a)):
for j in range(len(a)-i-1):
if (a[j] > a[j+1]):
a[j], a[j+1] = a[j+1], a[j]
插入排序
def insertSort(a):
for i in range(len(a)):
min = i
for j in range(i+1, len(a)):
if a[min] > a[j]:
min = j
a[i], a[min] = a[min], a[i]
希尔排序(升级版插入排序)
def shellSort(a):
gap = len(a)//2
while gap > 0:
for i in range(gap, len(a)):
j = i
current = a[i]
while j - gap >= 0 and current < a[j-gap]:
a[j] = a[j-gap]
j -= gap
a[j] = current
gap //= 2
快速排序
def quickSort(a):
if len(a) < 2:
return a
else:
pivot = a[0]
less = [i for i in a[1:] if i <= pivot]
greater = [i for i in a[1:] if i > pivot]
return quickSort(less) + [pivot] + quickSort(greater)

a = quickSort(a)

绘制的逻辑

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

flowchart TB
subgraph 排序过程
擦除上一帧的画面--"plt.cla()"--->绘制当前的散点--"plt.scatter(x,y,s,c)"--->暂停一个时长--"进入新的周期"-->擦除上一帧的画面
end
暂停一个时长--排序结束后-->a["plt.show()<br>plt.close()"]

那么代码就很简单了:

plt.cla()
x = range(0, 100)
plt.scatter(a, x, color="00", s=2)
plt.pause(0.01)

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

plt.show()
plt.close()

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


后记

完整代码示例

import random
import matplotlib.pyplot as plt


def initList():
a = list(range(100))
a = random.sample(a, k=100)
return a


def draw_frame(a):
plt.cla()
x = list(range(100))
plt.scatter(x, a, color="00", s=2)
plt.pause(0.01)


def bubbleSort(a):
for i in range(len(a)-1):
for j in range(len(a)-i-1):
if a[j] > a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
draw_frame(a)


def partition(a, low, high):
draw_frame(a)
i = (low-1)
pivot = a[high]

for j in range(low, high):
if a[j] <= pivot:

i = i+1
a[i], a[j] = a[j], a[i]

a[i+1], a[high] = a[high], a[i+1]

return (i+1)


def quickSort(a, low, high):
if low < high:

pi = partition(a, low, high)

quickSort(a, low, pi-1)
quickSort(a, pi+1, high)


def insertSort(a):
for i in range(len(a)):
min = i
for j in range(i+1, len(a)):
if a[min] > a[j]:
min = j
a[i], a[min] = a[min], a[i]
draw_frame(a)


def shellSort(a):
gap = len(a)//2
while gap > 0:
for i in range(gap, len(a)):
j = i
current = a[i]
while j - gap >= 0 and current < a[j-gap]:
a[j] = a[j-gap]
j -= gap
a[j] = current
draw_frame(a)
gap //= 2


shellSort(initList())
bubbleSort(initList())
quickSort(initList(), 0, len(initList())-1)

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

import random
import matplotlib.pyplot as plt
import copy
import matplotlib.animation as animation


class method:
name = ""

def init_list(self):
a = list(range(-100, 100))
a = random.sample(a, k=len(a))
return a

def bubble_sort(self, data, store):
a = copy.deepcopy(data)
for i in range(len(a)-1):
for j in range(len(a)-i-1):
if a[j] > a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
c = copy.deepcopy(a)
store.append(c)

def shell_sort(self, data, store):
gap = len(data)//2
while gap > 0:
for i in range(gap, len(data)):
j = i
current = data[i]
while j - gap >= 0 and current < data[j-gap]:
data[j] = data[j-gap]
j -= gap
data[j] = current
c = copy.deepcopy(data)
store.append(c)
gap //= 2

def insert_sort(self, data, store):
for i in range(len(data)):
min_pos = i
for j in range(i+1, len(data)):
if data[min_pos] > data[j]:
min_pos = j
data[i], data[min_pos] = data[min_pos], data[i]
c = copy.deepcopy(data)
store.append(c)

def partition(self, a, low, high):
c = copy.deepcopy(a)
store.append(c)
i = (low-1)
pivot = a[high]

for j in range(low, high):
if a[j] <= pivot:
i = i+1
a[i], a[j] = a[j], a[i]

a[i+1], a[high] = a[high], a[i+1]

return (i+1)

def quick_sort(self, data, low, high, store):

if low < high:
pi = self.partition(data, low, high)
self.quick_sort(data, low, pi-1, store)
self.quick_sort(data, pi+1, high, store)

def update_frames(self, n):
plt.cla()
plt.xticks([])
plt.yticks([])
plt.axis('off')
plt.title(self.name)
x = range(-100, 100)
plt.scatter(x, store[n], s=2, color="00")

def making_animation(self, name, store):
self.name = name
fig = plt.figure(num=1, dpi=100)
fig.add_subplot(1, 1, 1)
ani = animation.FuncAnimation(
fig, self.update_frames, interval=80, blit=False, repeat=False, frames=int(len(store)))
ani.save('%s.gif' % name, writer="ffmpeg", progress_callback=lambda i,
n: print(name+"Processing"+str(int(i/n*100))+"%"))
fig.clf()
store = []
return store


if __name__ == '__main__':

methods = method()
store = []
a = methods.init_list()
data = copy.deepcopy(a)

methods.bubble_sort(data, store)
store = methods.making_animation("BubbleSort", store)

data = copy.deepcopy(a)
methods.quick_sort(data, 0, len(data)-1, store)
store = methods.making_animation("QuickSort", store)

data = copy.deepcopy(a)
methods.shell_sort(data, store)
store = methods.making_animation("ShellSort", store)

data = copy.deepcopy(a)
methods.insert_sort(data, store)
store = methods.making_animation("InsertSort", store)

shellSort

insertSort

bubbleSort

quickSort

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

import random
import matplotlib.pyplot as plt
import copy
import matplotlib.animation as animation


class method:
name = ""
mark = []

def init_list(self):
a = list(range(0, 100))
a = random.sample(a, k=len(a))
return a

def bubble_sort(self, data, store):
a = copy.deepcopy(data)
for i in range(len(a)-1):
for j in range(len(a)-i-1):
if a[j] > a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
self.mark.append(j)
c = copy.deepcopy(a)
store.append(c)

def shell_sort(self, data, store):
gap = len(data)//2
while gap > 0:
for i in range(gap, len(data)):
j = i
current = data[i]
while j - gap >= 0 and current < data[j-gap]:
data[j] = data[j-gap]
j -= gap
data[j] = current
self.mark.append(j)
c = copy.deepcopy(data)
store.append(c)

gap //= 2

def insert_sort(self, data, store):
for i in range(len(data)):
min_pos = i
for j in range(i+1, len(data)):
if data[min_pos] > data[j]:
min_pos = j
self.mark.append(j)
data[i], data[min_pos] = data[min_pos], data[i]
c = copy.deepcopy(data)
store.append(c)

def partition(self, a, low, high):
c = copy.deepcopy(a)
store.append(c)
i = (low-1)
pivot = a[high]

for j in range(low, high):
if a[j] <= pivot:
i = i+1
a[i], a[j] = a[j], a[i]
self.mark.append(j)
a[i+1], a[high] = a[high], a[i+1]

return (i+1)

def quick_sort(self, data, low, high, store):

if low < high:
pi = self.partition(data, low, high)
self.quick_sort(data, low, pi-1, store)
self.quick_sort(data, pi+1, high, store)

def update_frames(self, n):
plt.cla()
plt.xticks([])
plt.yticks([])
plt.axis('off')
plt.title(self.name)
x = range(0, 100)
plt.bar(x, store[n])
plt.bar(self.mark[n], len(store[n]), color="red")

def making_animation(self, name, store):
self.name = name
fig = plt.figure(num=1, dpi=100)
fig.add_subplot(1, 1, 1)
ani = animation.FuncAnimation(
fig, self.update_frames, interval=80, blit=False, repeat=False, frames=int(len(store)))
ani.save('%s.gif' % name, writer="ffmpeg", progress_callback=lambda i,
n: print(name+"Processing"+str(int(i/n*100))+"%"))
fig.clf()
store = []
return store


if __name__ == '__main__':

methods = method()
store = []
a = methods.init_list()
data = copy.deepcopy(a)

methods.mark = []
methods.bubble_sort(data, store)
store = methods.making_animation("BubbleSort", store)

methods.mark = []
data = copy.deepcopy(a)
methods.quick_sort(data, 0, len(data)-1, store)
store = methods.making_animation("QuickSort", store)

methods.mark = []
data = copy.deepcopy(a)
methods.shell_sort(data, store)
store = methods.making_animation("ShellSort", store)

methods.mark = []
data = copy.deepcopy(a)
methods.insert_sort(data, store)
store = methods.making_animation("InsertSort", store)

效果如图:

bubbleSort

quickSort

shellSort

insertSort