[Python&科学计算]- matplotlib动画展

本文主要介绍，如何使用matplotlib动画展示3种基本的O(n^2)排序算法，希望能够帮助读者更好的理解这三种算法：

1. 冒泡排序
2. 插入排序
3. 选择排序
4. 总结

---

一、 冒泡排序

原理（by 百科）：

冒泡排序算法的运作如下：（从后往前）

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

matplotlib 代码：

#-*- coding:utf-8 -*-
#copyright@zhangggugu
from matplotlib import pyplot as plt
import matplotlib.animation as animation
import numpy as np


def data_gen_bubble_sort():
    for i in range(len(data_to_be_sorted)):
        for j in range(0, len(data_to_be_sorted)-i-1):
            if data_to_be_sorted[j] > data_to_be_sorted[j+1]:
                # exchange the corresponding data
                data_to_be_sorted[j], data_to_be_sorted[j+1] = data_to_be_sorted[j+1], data_to_be_sorted[j] 
                yield data_to_be_sorted
        # corted part set color to color sorted
        lines[len(data_to_be_sorted)-i-1].set_color(color_sorted)
        yield data_to_be_sorted

def update(data):
    """
    这里面获取到的data来自 data_gen返回的数据
    """
    for i in xrange(len(data)):
        lines[i].set_ydata([0, data[i]])

    return lines


def init():
    ax.set_ylim(-1, max_val)
    ax.set_xlim(-1, n+1)
    return 


color_original = '#ff9999'
color_sorted = '#9999ff'
color_selected = '#99ff99'

n = 20
max_val = 50
# 产生 n 个 0到50之间的数
data_to_be_sorted = np.random.rand(n)*max_val

fig, ax = plt.subplots()

xdata = [[i+1 for i in xrange(n)], [i+1 for i in xrange(n)]]
ydata = [[0 for i in xrange(n)], data_to_be_sorted]

lines = ax.plot(xdata, ydata, lw=2, c=color_original)


#print lines[0].__str__


ani = animation.FuncAnimation(fig, update, data_gen_bubble_sort, interval=300,repeat=False, init_func=init)
#ani = animation.FuncAnimation(fig, update, data_gen_insert_sort, interval=300,repeat=False, init_func=init)
#ani = animation.FuncAnimation(fig, update, data_gen_select_sort, interval=300,repeat=False, init_func=init)

plt.show()

matplotlib 动画展示效果：
说明：蓝色的代表已经排好序的，粉红色的代表未排好序的。

图 1 冒泡排序展示

二、 插入排序

原理（by 百科）：

插入排序使用的是增量方法；在排好子数组A[1..j-1]后，将A[j]插入，形成排好序的子数组A[1..j]；
步骤
⒈ 从有序数列{a1} 和无序数列 {a2,a3，…，an}开始进行排序；
⒉ 处理第i个元素时（i=2,3，…，n），数列{a1,a2，…，ai-1}是已有序的，而数列{ai,ai+1，…，an}是无序的。用ai与{a1,a2，…，ai-1}进行比较，找出合适的位置将ai插入；
⒊ 重复第二步，共进行n-i次插入处理，数列全部有序。

matplotlib 动画展示代码：
只需要把冒泡排序中的data_gen_bubble_sort换成下面的data_gen_insert_sort函数，然后将ani = animation.FuncAnimation(fig, update, data_gen_bubble_sort, interval=300,repeat=False, init_func=init) 的参数 data_gen_bubble_sort 换成 data_gen_insert_sort即可；

def data_gen_insert_sort():
    for i in range(0,len(data_to_be_sorted)):
        for j in range(i, 0, -1):
            if data_to_be_sorted[j] < data_to_be_sorted[j-1]:
                # exchange the corresponding data
                data_to_be_sorted[j], data_to_be_sorted[j-1] = data_to_be_sorted[j-1], data_to_be_sorted[j] 
                yield data_to_be_sorted
        # corted part set color to color sorted
        lines[i].set_color(color_sorted)
        yield data_to_be_sorted

matplotlib 动画展示效果：
说明：蓝色的代表已经排好序的，粉红色的代表未排好序的。

图 2 插入排序展示

三、 选择排序

原理：
你可以想象一下在斗地主的时候，你一张一张把扑克牌抓上来，然后你拿一张上来就会将其放入到正确的位置-比如你手上已经有3和5这两张牌，这个时候你抓到4，那么3和5之间就是4这张牌的正确位置，就这样，当你抓完最后一张牌，你的整手扑克牌也就是已经拍好序了，这个就是排序算法的基本原理！

matplotlib 代码：
只需要把冒泡排序中的data_gen_bubble_sort换成下面的data_gen_select_sort函数，然后将ani = animation.FuncAnimation(fig, update, data_gen_bubble_sort, interval=300,repeat=False, init_func=init) 的参数 data_gen_bubble_sort 换成 data_gen_select_sort即可；

def data_gen_select_sort():
    for i in range(0,len(data_to_be_sorted)):
        minimum = data_to_be_sorted[i]
        minimun_index = i
        # corted part set color to color sorted
        lines[i].set_color(color_sorted)
        for j in range(i, len(data_to_be_sorted)):
            
            # reset the color of the unsorted lines
            for index in range(i+1, len(data_to_be_sorted)):
                lines[index].set_color(color_original)

            if data_to_be_sorted[j] < minimum:
                #exchange the minimun value
                minimum = data_to_be_sorted[j]
                minimun_index = j
                lines[minimun_index].set_color(color_selected)
                yield data_to_be_sorted

        data_to_be_sorted[i], data_to_be_sorted[minimun_index] = data_to_be_sorted[minimun_index], data_to_be_sorted[i] 
        yield data_to_be_sorted

matplotlib 动画展示效果：
说明：蓝色的代表已经排好序的部分，青色代表剩余部分中最小的元素，粉红色的代表未排好序的部分。

图 3 插入排序效果

四、 总结

这几天在网易云课堂中学习python中matplotlib这个库的使用，学到animation，有个作业是用动画展示冒泡排序，所以在完成作业的同时，把另外两种同类的排序算法也展示一下了，如果你想在电脑上面运行该文件，请确定已经安装好了Python环境和Anaconda集成环境（或者安装有科学计算包python 虚拟环境），学习愉快！

课程链接：http://study.163.com/course/courseMain.htm?courseId=1050010
老师的课程讲练结合，个人感觉挺不错的，感兴趣的同学可以看看哦！

声明：

1. 联系作者，新浪微博私信 @谷谷_z
2. 如果在文章当中发现有描述错误的地方，还请您不吝指出，万分感谢！
3. 此文章系本人原创作品，转发请注明出处！