专栏首页算法channel厉害了!Python+matplotlib制作8个排序算法的动画

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

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表示展示排序的动画,其他两个选项:保存htmlmp4

  • 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,以及 matplotlibanimation功能,剩下的就是手动实现的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)

我已经执行完8个排序算法,录制了3个动画,效果如下:

1) 快速排序

2) 归并排序

3) 堆排序

项目地址,这里面有完整源码:

https://github.com/zamhown/sorting-visualizer

本文分享自微信公众号 - Python与机器学习算法频道(alg-channel),作者:zglg

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python|获取对象的类型,方法,setattr()添加属性

    01 基本类型 基本类型都可以用type()判断: >>> type(123) <class 'int'> >>> type('str') <class 's...

    double
  • 原创系列 |「冒泡排序」提升为「快速排序」,都发生了什么?

    彻底弄明白常用的排序算法的基本思想,算法的时间和空间复杂度,以及如何选择这些排序算法,确定要解决的问题的最佳排序算法,我们先总结下冒泡排序和其改进后的快速排序这...

    double
  • 冒泡排序到快速排序做的那些优化

    本公众号主要推送关于对算法的思考以及应用的消息。算法思想说来有,分而治之,搜索,动态规划,回溯,贪心等,结合这些思想再去思考如今很火的大数据,云计算和机器学习,...

    double
  • flask flask-login实现用户登陆认证的详细过程(flask 53)

    用户认证的原理 在了解使用Flask来实现用户认证之前,我们首先要明白用户认证的原理。假设现在我们要自己去实现用户认证,需要做哪些事情呢?

    用户5760343
  • 海量数据处理问题知识点复习手册

    https://blog.csdn.net/v_july_v/article/details/6279498

    后端技术漫谈
  • 那些年我们一起追过的缓存写法(四)

    蘑菇先生
  • springBoot Actuator 健康监测

    spring boot 微服务作为一项在云中部署应用和服务的新技术是当下比较热门话题,而微服务的特点决定了功能模块的部署是分布式的,运行在不同的机器上相互通过服...

    chinotan
  • ie6,ie7,ff 的css兼容hack写法

    Code <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www....

    菩提树下的杨过
  • 谷歌大脑研究:AI识别蛋白质结晶,准确率高达94%

    谷歌大脑团队的成员今天宣布开发了用于识别蛋白质结晶的深层卷积神经网络,准确率约为94%。蛋白质结晶决定了细胞的形状,可以在发现治疗各种疾病的药物中发挥作用。它们...

    AiTechYun
  • 反射类的main方法

    有时候我们需要调用一个类的Main方法,也可说是执行这个类的代码。但是这时候这个类我们还没有写好,或者这个类是通过网络运行时传给我们的,我们就不可能在程序中知道...

    MonroeCode

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动