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)

参数说明：

必需参数，确定散点的横纵坐标，支持传入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)

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

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)