本文主要介绍，如何使用matplotlib动画展示3种基本的O(n^2)排序算法，希望能够帮助读者更好的理解这三种算法：
- 冒泡排序
- 插入排序
- 选择排序
- 总结
一、 冒泡排序
原理（by 百科）：
冒泡排序算法的运作如下：（从后往前）
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
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
老师的课程讲练结合，个人感觉挺不错的，感兴趣的同学可以看看哦！
声明：
- 联系作者，新浪微博私信 @谷谷_z
- 如果在文章当中发现有描述错误的地方，还请您不吝指出，万分感谢！
- 此文章系本人原创作品，转发请注明出处！
网友评论