Python排序算法可视化

前言

在为大一同学们写C语言期末复习指南时，在菜鸟教程上看到了几幅排序算法的散点动图，感觉很有意思，并且立即想到了之前参加焦糖招新的时候用过的matplotlib可视化库，尝试实现一下各种算法。

正文

话不多说，立即开始尝试：

准备工作

简单想了一下，在matplotlib库提供的几种不同的图形中，散点图可能会最为直观，翻阅doc可以找到相关的函数：

matplotlib.pyplot.scatter(x, y, s=None, c=None, marker=None, cmap=None, norm=None, vmin=None, vmax=None, alpha=None, linewidths=None, verts=<deprecated parameter>, edgecolors=None, *, plotnonfinite=False, data=None, **kwargs)

参数说明：

必需参数，确定散点的横纵坐标，支持传入array(也就是说可以传入两个列表来直接画出所有的点)
s: float or array-like,shapr(n,),optinal
可选项，控制各个散点的大小
c: array-like or list of colors or color, optional
可选项，控制散点颜色

更多的参数项似乎很难用得到，于是这里就不写了。

思路确立

第一次建立的初期思路如下：

看起来一切进展还算顺利，然而到了逐帧绘制合成时，问题出现了。

我们回头看看FuncAnimation函数的参数说明：

class matplotlib.animation.FuncAnimation(fig, func, frames=None, init_func=None, fargs=None, save_count=None, *, cache_frame_data=True, **kwargs)

fig是要选取的图变量，func是每一帧的更新函数

FuncAnimation调用func来绘制每一帧画面，可我们的排序算法是一个循环的过程，我们需要展示的是每次循环的结果，也就是我们绘制每一帧的过程是在排序过程中发生的，FuncAnimation无法直接穿透循环过程来得到每一帧的数据，用这种方法来更新每一帧将遇到巨大的困难。

那么如何解决这个问题呢？

两个思路：

1.将循环过程中每一帧的数据保存在列表中，在最后调用func的时候来遍历数组绘图
2.抛弃FuncAnimation函数，自己逐帧绘制

第一个思路乍看起来还不错，但如果数据量较大，将占用大量的内存来存储数据。

所以我决定使用第二个思路，自己绘制每一帧的画面。

修改后的思路为：

按照这个思路，我们从头开始构建：

生成连续随机数列表


xxxxxxxxxx
3
1
import random
2
a = list(range(100))
3
a = random.sample(a,k = 100)

这里直接生成了一组0~99的数据，为了保证排序结束的散点图是一条直线，要避免生成重复的随机数，所以调用random.sample

构建排序算法

冒泡排序


xxxxxxxxxx
5
1
def bubbleSort(a):
2
    for i in range(len(a)):
3
        for j in range(len(a)-i-1):
4
            if (a[j] > a[j+1]):
5
                a[j], a[j+1] = a[j+1], a[j]

插入排序


xxxxxxxxxx
7
1
def insertSort(a):
2
    for i in range(len(a)):
3
        min = i
4
        for j in range(i+1, len(a)):
5
            if a[min] > a[j]:
6
                min = j
7
        a[i], a[min] = a[min], a[i]

希尔排序(升级版插入排序)


xxxxxxxxxx
11
1
def shellSort(a):
2
    gap = len(a)//2
3
    while gap > 0:
4
        for i in range(gap, len(a)):
5
            j = i
6
            current = a[i]
7
            while j - gap >= 0 and current < a[j-gap]:
8
                a[j] = a[j-gap]
9
                j -= gap
10
                a[j] = current
11
        gap //= 2

快速排序


xxxxxxxxxx
10
1
def quickSort(a):
2
    if len(a) < 2:
3
        return a
4
    else:
5
        pivot = a[0]
6
        less = [i for i in a[1:] if i <= pivot]
7
        greater = [i for i in a[1:] if i > pivot]
8
        return quickSort(less) + [pivot] + quickSort(greater)
9
10
a = quickSort(a)

绘制的逻辑

要做到自己绘制每一帧，我们需要按照这样的逻辑来执行：

那么代码就很简单了：


xxxxxxxxxx
4
1
plt.cla()
2
x = range(0, 100)
3
plt.scatter(a, x, color="00", s=2)
4
plt.pause(0.01)

将这段代码放置到能体现排序算法特点的循环周期内，在循环结束依次后展示所有的画面：


xxxxxxxxxx
2
1
plt.show()
2
plt.close()

至此，可视化过程就已经实现了。

后记

完整代码示例


xxxxxxxxxx
77
1
import random
2
import matplotlib.pyplot as plt
3
4
5
def initList():
6
    a = list(range(100))
7
    a = random.sample(a, k=100)
8
    return a
9
10
11
def draw_frame(a):
12
    plt.cla()
13
    x = list(range(100))
14
    plt.scatter(x, a, color="00", s=2)
15
    plt.pause(0.01)
16
17
18
def bubbleSort(a):
19
    for i in range(len(a)-1):
20
        for j in range(len(a)-i-1):
21
            if a[j] > a[j+1]:
22
                a[j], a[j+1] = a[j+1], a[j]
23
        draw_frame(a)
24
25
26
def partition(a, low, high):
27
    draw_frame(a)
28
    i = (low-1)
29
    pivot = a[high]
30
31
    for j in range(low, high):
32
        if a[j] <= pivot:
33
34
            i = i+1
35
            a[i], a[j] = a[j], a[i]
36
37
    a[i+1], a[high] = a[high], a[i+1]
38
39
    return (i+1)
40
41
42
def quickSort(a, low, high):
43
    if low < high:
44
45
        pi = partition(a, low, high)
46
47
        quickSort(a, low, pi-1)
48
        quickSort(a, pi+1, high)
49
50
51
def insertSort(a):
52
    for i in range(len(a)):
53
        min = i
54
        for j in range(i+1, len(a)):
55
            if a[min] > a[j]:
56
                min = j
57
        a[i], a[min] = a[min], a[i]
58
        draw_frame(a)
59
60
61
def shellSort(a):
62
    gap = len(a)//2
63
    while gap > 0:
64
        for i in range(gap, len(a)):
65
            j = i
66
            current = a[i]
67
            while j - gap >= 0 and current < a[j-gap]:
68
                a[j] = a[j-gap]
69
                j -= gap
70
                a[j] = current
71
            draw_frame(a)
72
        gap //= 2
73
74
75
shellSort(initList())
76
bubbleSort(initList())
77
quickSort(initList(), 0, len(initList())-1)

更加简洁和有效的代码，直接将gif保存到本地：


xxxxxxxxxx
112
1
import random
2
import matplotlib.pyplot as plt
3
import copy
4
import matplotlib.animation as animation
5
6
7
class method:
8
    name = ""
9
10
    def init_list(self):
11
        a = list(range(-100, 100))
12
        a = random.sample(a, k=len(a))
13
        return a
14
15
    def bubble_sort(self, data, store):
16
        a = copy.deepcopy(data)
17
        for i in range(len(a)-1):
18
            for j in range(len(a)-i-1):
19
                if a[j] > a[j+1]:
20
                    a[j], a[j+1] = a[j+1], a[j]
21
            c = copy.deepcopy(a)
22
            store.append(c)
23
24
    def shell_sort(self, data, store):
25
        gap = len(data)//2
26
        while gap > 0:
27
            for i in range(gap, len(data)):
28
                j = i
29
                current = data[i]
30
                while j - gap >= 0 and current < data[j-gap]:
31
                    data[j] = data[j-gap]
32
                    j -= gap
33
                    data[j] = current
34
                c = copy.deepcopy(data)
35
                store.append(c)
36
            gap //= 2
37
38
    def insert_sort(self, data, store):
39
        for i in range(len(data)):
40
            min_pos = i
41
            for j in range(i+1, len(data)):
42
                if data[min_pos] > data[j]:
43
                    min_pos = j
44
            data[i], data[min_pos] = data[min_pos], data[i]
45
            c = copy.deepcopy(data)
46
            store.append(c)
47
48
    def partition(self, a, low, high):
49
        c = copy.deepcopy(a)
50
        store.append(c)
51
        i = (low-1)
52
        pivot = a[high]
53
54
        for j in range(low, high):
55
            if a[j] <= pivot:
56
                i = i+1
57
                a[i], a[j] = a[j], a[i]
58
59
        a[i+1], a[high] = a[high], a[i+1]
60
61
        return (i+1)
62
63
    def quick_sort(self, data, low, high, store):
64
65
        if low < high:
66
            pi = self.partition(data, low, high)
67
            self.quick_sort(data, low, pi-1, store)
68
            self.quick_sort(data, pi+1, high, store)
69
70
    def update_frames(self, n):
71
        plt.cla()
72
        plt.xticks([])
73
        plt.yticks([])
74
        plt.axis('off')
75
        plt.title(self.name)
76
        x = range(-100, 100)
77
        plt.scatter(x, store[n], s=2, color="00")
78
79
    def making_animation(self, name, store):
80
        self.name = name
81
        fig = plt.figure(num=1, dpi=100)
82
        fig.add_subplot(1, 1, 1)
83
        ani = animation.FuncAnimation(
84
            fig, self.update_frames, interval=80, blit=False, repeat=False, frames=int(len(store)))
85
        ani.save('%s.gif' % name, writer="ffmpeg", progress_callback=lambda i,
86
                 n: print(name+"Processing"+str(int(i/n*100))+"%"))
87
        fig.clf()
88
        store = []
89
        return store
90
91
92
if __name__ == '__main__':
93
94
    methods = method()
95
    store = []
96
    a = methods.init_list()
97
    data = copy.deepcopy(a)
98
99
    methods.bubble_sort(data, store)
100
    store = methods.making_animation("BubbleSort", store)
101
102
    data = copy.deepcopy(a)
103
    methods.quick_sort(data, 0, len(data)-1, store)
104
    store = methods.making_animation("QuickSort", store)
105
106
    data = copy.deepcopy(a)
107
    methods.shell_sort(data, store)
108
    store = methods.making_animation("ShellSort", store)
109
110
    data = copy.deepcopy(a)
111
    methods.insert_sort(data, store)
112
    store = methods.making_animation("InsertSort", store)

shellSort

insertSort

bubbleSort

quickSort

简单修改一下图形绘制模式，把散点图修改为柱状图，可以很容易得到柱状图形式的排序动画：


x
1
import random
2
import matplotlib.pyplot as plt
3
import copy
4
import matplotlib.animation as animation
5
6
7
class method:
8
    name = ""
9
    mark = []
10
11
    def init_list(self):
12
        a = list(range(0, 100))
13
        a = random.sample(a, k=len(a))
14
        return a
15
16
    def bubble_sort(self, data, store):
17
        a = copy.deepcopy(data)
18
        for i in range(len(a)-1):
19
            for j in range(len(a)-i-1):
20
                if a[j] > a[j+1]:
21
                    a[j], a[j+1] = a[j+1], a[j]
22
                    self.mark.append(j)
23
            c = copy.deepcopy(a)
24
            store.append(c)
25
26
    def shell_sort(self, data, store):
27
        gap = len(data)//2
28
        while gap > 0:
29
            for i in range(gap, len(data)):
30
                j = i
31
                current = data[i]
32
                while j - gap >= 0 and current < data[j-gap]:
33
                    data[j] = data[j-gap]
34
                    j -= gap
35
                    data[j] = current
36
                    self.mark.append(j)
37
                c = copy.deepcopy(data)
38
                store.append(c)
39
40
            gap //= 2
41
42
    def insert_sort(self, data, store):
43
        for i in range(len(data)):
44
            min_pos = i
45
            for j in range(i+1, len(data)):
46
                if data[min_pos] > data[j]:
47
                    min_pos = j
48
                    self.mark.append(j)
49
            data[i], data[min_pos] = data[min_pos], data[i]
50
            c = copy.deepcopy(data)
51
            store.append(c)
52
53
    def partition(self, a, low, high):
54
        c = copy.deepcopy(a)
55
        store.append(c)
56
        i = (low-1)
57
        pivot = a[high]
58
59
        for j in range(low, high):
60
            if a[j] <= pivot:
61
                i = i+1
62
                a[i], a[j] = a[j], a[i]
63
                self.mark.append(j)
64
        a[i+1], a[high] = a[high], a[i+1]
65
66
        return (i+1)
67
68
    def quick_sort(self, data, low, high, store):
69
70
        if low < high:
71
            pi = self.partition(data, low, high)
72
            self.quick_sort(data, low, pi-1, store)
73
            self.quick_sort(data, pi+1, high, store)
74
75
    def update_frames(self, n):
76
        plt.cla()
77
        plt.xticks([])
78
        plt.yticks([])
79
        plt.axis('off')
80
        plt.title(self.name)
81
        x = range(0, 100)
82
        plt.bar(x, store[n])
83
        plt.bar(self.mark[n], len(store[n]), color="red")
84
85
    def making_animation(self, name, store):
86
        self.name = name
87
        fig = plt.figure(num=1, dpi=100)
88
        fig.add_subplot(1, 1, 1)
89
        ani = animation.FuncAnimation(
90
            fig, self.update_frames, interval=80, blit=False, repeat=False, frames=int(len(store)))
91
        ani.save('%s.gif' % name, writer="ffmpeg", progress_callback=lambda i,
92
                 n: print(name+"Processing"+str(int(i/n*100))+"%"))
93
        fig.clf()
94
        store = []
95
        return store
96
97
98
if __name__ == '__main__':
99
100
    methods = method()
101
    store = []
102
    a = methods.init_list()
103
    data = copy.deepcopy(a)
104
105
    methods.mark = []
106
    methods.bubble_sort(data, store)
107
    store = methods.making_animation("BubbleSort", store)
108
109
    methods.mark = []
110
    data = copy.deepcopy(a)
111
    methods.quick_sort(data, 0, len(data)-1, store)
112
    store = methods.making_animation("QuickSort", store)
113
114
    methods.mark = []
115
    data = copy.deepcopy(a)
116
    methods.shell_sort(data, store)
117
    store = methods.making_animation("ShellSort", store)
118
119
    methods.mark = []
120
    data = copy.deepcopy(a)
121
    methods.insert_sort(data, store)
122
    store = methods.making_animation("InsertSort", store)
123

效果如图：

bubbleSort

quickSort

shellSort

insertSort