用 manim 写一个排序算法动画

本文不介绍 manim 的安装教程，需要安装教程的请参考：https://docs.manim.org.cn/getting_started/installation.html

什么是 manim

Manim 是一个用于精确编程动画的引擎，专为创建解释性数学视频而设计。

有两个主要版本：

• 3b1b/manim 【最新版，3Blue1Brown 原版】
• ManimCommunity/manim 【社区版，更稳定，更易上手】

冒泡排序介绍

冒泡排序（Bubble Sort）重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来，直到没有再需要交换为止。

算法步骤：

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

初始化元素

比如我们需要排序数组为：[4,2,3,1,5]

首先在 manim 场景上初始化需要排序的所有元素，用矩形来表示，通过设置不同的高度来表示不同的元素大小。

from manimlib import *

class Test(Scene):
    def construct(self):
        COLOR = [BLUE, GREEN, RED, PINK, ORANGE, MAROON_B, TEAL, PURPLE_B, GREY_BROWN]
        arr = [4,2,3,1,5]
        g = VGroup()
        for i in range(len(arr)):
            r1=Rectangle(width=1,height=arr[i],fill_color=COLOR[i%len(COLOR)],fill_opacity=1)
            t1=Text(str(arr[i])).scale(0.5)
            rec = VGroup(r1,t1)
            g.add(rec)

        g.arrange(RIGHT,aligned_edge=DOWN)
        self.add(g)
        self.wait()

运行：

manimgl main.py BubbleSort

运行后会出现一个窗口显示如下画面：

g.arrange(RIGHT, aligned_edge=DOWN) 中，RIGHT 表示所有元素向右依次排列，aligned_edge=DOWN 将底边对齐。

元素交换动画

一开始用 manim 提供的 CyclicReplace 方法来交换两个元素：

self.play(CyclicReplace(g[0], g[1]))
self.wait()

交换是交换了，但是交换后对齐的边变成了顶部对齐，不符合预期。

最终决定使用元素的 target 属性来制作交换动画：

g[0].generate_target()
g[0].target.next_to(g[1],ORIGIN,aligned_edge=DOWN)

g[1].generate_target()
g[1].target.next_to(g[0],ORIGIN,aligned_edge=DOWN)

self.play(MoveToTarget(g[0]),MoveToTarget(g[1]))

generate_target() 生成元素的 target，next_to() 将元素移动到指定位置，ORIGIN 表示目标元素所在位置。

完美符合预期。

实现代码

这里在初始化场景元素时，额外添加了一个数组来存放所有场景元素，因为在交换元素位置后，也要交换对应索引下的元素。如果直接用 VGroup 来交换会出现问题：

TypeError: 'VGroup' object does not support item assignment

还添加了 Indicate 方法，当涉及到对应交换的元素时，会做一个类似对焦的动作。

from manimlib import *

class BubbleSort(Scene):
    def construct(self):
        self.COLOR = [BLUE, GREEN, RED, PINK, ORANGE, MAROON_B, TEAL, PURPLE_B, GREY_BROWN]
        self.bubbleSort([4,2,3,1,5])

    def init_vmobj(self,arr):
        self.vmArr = []
        g = VGroup()
        for i in range(len(arr)):
            r1=Rectangle(width=1,height=arr[i]/2,fill_color=self.COLOR[i%len(self.COLOR)],fill_opacity=1)
            t1=Text(str(arr[i])).scale(0.5)
            rec = VGroup(r1,t1)
            self.vmArr.append(rec)
            g.add(rec)
        g.arrange(RIGHT,aligned_edge=DOWN)
        self.add(g)
        self.wait()

    def bubbleSort(self,arr):
        self.init_vmobj(arr)
        for i in range(1, len(arr)):
            for j in range(0, len(arr)-i):
                self.play(Indicate(self.vmArr[j]))
                self.play(Indicate(self.vmArr[j+1],color=RED))
                if arr[j] > arr[j+1]:
                    arr[j], arr[j + 1] = arr[j + 1], arr[j]
                    self.cyc_move(self.vmArr[j],self.vmArr[j+1])
                    self.vmArr[j],self.vmArr[j+1] = self.vmArr[j+1],self.vmArr[j]
        return arr

    def cyc_move(self,vm1,vm2):
        vm1.generate_target()
        vm1.target.next_to(vm2,ORIGIN,aligned_edge=DOWN)

        vm2.generate_target()
        vm2.target.next_to(vm1,ORIGIN,aligned_edge=DOWN)

        self.play(MoveToTarget(vm1),MoveToTarget(vm2))
        self.wait()