【算法动画】厉害了！Python+matplotlib制作8个排序算法的动画

Python数据科学 2020-09-13

The following article is from Python与算法社区 Author zglg

点击上方“Python数据科学”，星标公众号

重磅干货，第一时间送达

☞500g+超全学习资源免费领取

1 算法的魅力

深刻研究排序算法是入门算法较为好的一种方法，现在还记得4年前手动实现常见8种排序算法，通过随机生成一些数据，逐个校验代码实现的排序过程是否与预期的一致，越做越有劲，越有劲越想去研究，公交车上，吃饭的路上。。。那些画面，现在依然记忆犹新。

能力有限，当时并没有生成排序过程的动画，所以这些年想着抽时间一定把排序的过程都制作成动画，然后分享出来，让更多的小伙伴看到，通过排序算法的动态演示动画，找到学习算法的真正乐趣，从而迈向一个新的认知领域。

当时我还是用C++写的，时过境迁，Python迅速崛起，得益于Python的简洁，接口易用，最近终于有人在github中开源了使用Python动画展示排序算法的项目，真是倍感幸运。

动画还是用matplotlib做出来的，这就更完美了，一边学完美的算法，一边还能提升Python熟练度，一边还能学到使用matplotlib制作动画。

2 完美的答案

这个库一共演示8个常见的排序算法：

bubble-sort : Only show the visualization of bubble sorting algorithm in the animation. The following arguments have similar functions.
comb-sort
heap-sort
insertion-sort
merge-sort
quick-sort
selection-sort
shell-sort

启动的脚本是output.py，脚本的参数有三类，下面逐个解释。

python output.py play heap-sort reversed

play表示展示排序的动画，其他两个选项：保存html和mp4

play : Play an animation of a specific sorting algorithm or all algorithms in a new window, as a "figure" to Matplotlib.
save-html : Save the animation as a HTML page with a sequence of images.
save-mp4 : Save the animation as a MP4 video.

heap-sort表示堆排序，就是此次执行脚本你想看哪个排序算法的动画展示,设置为quick-sort表示查看快排动画, all表示所有排序算法一次展示。

reversed 这类参数是我重点想说的，这类参数还有如下其他几个选项。通常说一个快排平均时间复杂度为nlog2n，为什么是平均呢？

我们很难找到一个真正100%准确的函数t，输入data，通过t(data)计算出准确的理论执行时间，因为data的分布无法准确的拟合出来，而它又直接影响到实际的排序时间，比如输入一个几乎排序好的序列，一个没有重复元素的序列，一个随机序列，一个递减序列。所以只能根据某类分布给出大概的预估执行时间值。

almost-sorted : Sort an almost-sorted sequence.
few-unique : Sort a few-unique sequence.
random (default) : Sort a random sequence.
reversed : Sort a descending sequence.

3 动画展示

使用的模块和实例代码如下：

使用的包，主要是内置模块random, os, sys, re，以及 matplotlib的 animation功能，剩下的就是手动实现的8个排序算法。

import random
import os
import sys
import re
from matplotlib import pyplot as plt
from matplotlib import animation
from sorting.data import Data
from sorting.selectionsort import selection_sort
from sorting.bubblesort import bubble_sort
from sorting.insertionsort import insertion_sort
from sorting.shellsort import shell_sort
from sorting.mergesort import merge_sort
from sorting.quicksort import quick_sort
from sorting.heapsort import heap_sort
from sorting.combsort import comb_sort
from sorting.monkeysort import monkey_sort

快速排序代码，会保存所有的操作帧：

# Script Name     : quicksort.py
# Author          : Howard Zhang
# Created         : 14th June 2018
# Last Modified	  : 14th June 2018
# Version         : 1.0
# Modifications	  :
# Description     : Quick sorting algorithm.

import copy
from .data import Data

def quick_sort(data_set):
    # FRAME OPERATION BEGIN
    frames = [data_set]
    # FRAME OPERATION END
    ds = copy.deepcopy(data_set)
    qsort(ds, 0, Data.data_count, frames)
    # FRAME OPERATION BEGIN
    frames.append(ds)
    return frames
    # FRAME OPERATION END

def qsort(ds, head, tail, frames):
    if tail - head > 1:
        # FRAME OPERATION BEGIN
        ds_y = copy.deepcopy(ds)
        for i in range(head, tail):
            ds_y[i].set_color('y')
        # FRAME OPERATION END
        i = head
        j = tail - 1
        pivot = ds[j].value
        while i < j:
            # FRAME OPERATION BEGIN
            frames.append(copy.deepcopy(ds_y))
            frames[-1][i if ds[i].value == pivot else j].set_color('r')
            frames[-1][j if ds[i].value == pivot else i].set_color('k')
            # FRAME OPERATION END
            if ds[i].value > pivot or ds[j].value < pivot:
                ds[i], ds[j] = ds[j], ds[i]
                # FRAME OPERATION BEGIN
                ds_y[i], ds_y[j] = ds_y[j], ds_y[i]
                frames.append(copy.deepcopy(ds_y))
                frames[-1][i if ds[i].value == pivot else j].set_color('r')
                frames[-1][j if ds[i].value == pivot else i].set_color('k')
                # FRAME OPERATION END
            if ds[i].value == pivot:
                j -= 1
            else:
                i += 1
        qsort(ds, head, i, frames)
        qsort(ds, i+1, tail, frames)