快速排序动画展示

归并排序动画展示


堆排序动画展示


这些算法动画使用Matplotlib制作，接下来逐个补充。

学会第一部分如何制作动画后，可将此技术应用于排序算法调整过程的动态展示上。

首先生成测试使用的数据，待排序的数据个数至多`20个`，待排序序列为`random_wait_sort`，为每个值赋一个颜色值，这个由`random_rgb`负责：

data_count = 20 # here, max value of data_count is 20

random_wait_sort = [12, 34, 32, 24, 28, 39, 5,

22, 11, 25, 33, 32, 1, 25, 3, 8, 7, 1, 34, 7]

random_rgb = [(0.5, 0.811565104942967, 0.11211028937187217),

(0.5, 0.5201323831224014, 0.6660999602342474),

(0.5, 0.575976663060455, 0.17788242607567772),

(0.5, 0.6880174797416493, 0.43581701833249353),

(0.5, 0.4443131322001743, 0.6993600264279745),

(0.5, 0.5538835821863523, 0.889276053938713),

(0.5, 0.4851681185146841, 0.7977608586163772),

(0.5, 0.3886717808488436, 0.09319137949618972),

(0.5, 0.8952456581687489, 0.8282376936934484),

(0.5, 0.16360202854998007, 0.4538892160157194),

(0.5, 0.23233400128809478, 0.8544141586189615),

(0.5, 0.5224648797546528, 0.8194014475829123),

(0.5, 0.49396099968405016, 0.47441724394796825),

(0.5, 0.12078104526714728, 0.7715022079860492),

(0.5, 0.19428498518228154, 0.08174917157481443),

(0.5, 0.6058698403873457, 0.6085936584142663),

(0.5, 0.7801178568951216, 0.6414767240649862),

(0.5, 0.4768865661174162, 0.3889866229610085),

(0.5, 0.4301945092238082, 0.961688141676841),

(0.5, 0.40496648895289855, 0.24234095882836093)]

再封装一个简单的数据对象`Data`：

class Data:

def __init__(self, value, rgb):

self.value = value

self.color = rgb

# 造数据

@classmethod

def create(cls):

return [Data(val, rgb) for val, rgb in zip(random_wait_sort[:data_count],

random_rgb[:data_count])]

一旦发生调整，我们立即保存到帧列表`frames`中，注意此处需要`deepcopy`:

def bubble_sort(waiting_sort_data):

frames = [waiting_sort_data]

ds = copy.deepcopy(waiting_sort_data)

for i in range(data_count-1):

for j in range(data_count-i-1):

if ds[j].value > ds[j+1].value:

ds[j], ds[j+1] = ds[j+1], ds[j]

frames.append(copy.deepcopy(ds))

frames.append(ds)

return frames

实验结果图：


完整动画演示：


先上代码，比较经典，值得回味：

def quick_sort(data_set):

frames = [data_set]

ds = copy.deepcopy(data_set)

def qsort(head, tail):

if tail - head > 1:

i = head

j = tail - 1

pivot = ds[j].value

while i < j:

if ds[i].value > pivot or ds[j].value < pivot:

ds[i], ds[j] = ds[j], ds[i]

frames.append(copy.deepcopy(ds))

if ds[i].value == pivot:

j -= 1

else:

i += 1

qsort(head, i)

qsort(i+1, tail)

qsort(0, data_count)

frames.append(ds)

return frames

快速排序算法对输入为随机的序列优势往往较为明显，同样的输入数据，它只需要`24`帧调整就能完成排序：


选择排序和堆排序都是选择思维，但是性能却不如堆排序：

def selection_sort(data_set):

frames = [data_set]

ds = copy.deepcopy(data_set)

for i in range(0, data_count-1):

for j in range(i+1, data_count):

if ds[j].value < ds[i].value:

ds[i], ds[j] = ds[j], ds[i]

frames.append(copy.deepcopy(ds))

frames.append(ds)

return frames

同样的输入数据，它完成排序需要`108`帧:


动画展示如下，每轮会从未排序的列表中，挑出一个最小值，放到已排序序列后面。


堆排序大大改进了选择排序，逻辑上使用二叉树，先建立一个大根堆，然后根节点与未排序序列的最后一个元素交换，重新对未排序序列建堆。

完整代码如下：

def heap_sort(data_set):

frames = [data_set]

ds = copy.deepcopy(data_set)

def heap_adjust(head, tail):

i = head * 2 + 1 # head的左孩子

while i < tail:

if i + 1 < tail and ds[i].value < ds[i+1].value: # 选择一个更大的孩子

i += 1

if ds[i].value <= ds[head].value:

break

ds[head], ds[i] = ds[i], ds[head]

frames.append(copy.deepcopy(ds))

head = i

i = i * 2 + 1

# 建立一个最大堆，从最后一个父节点开始调整

for i in range(data_count//2-1, -1, -1):

heap_adjust(i, data_count)

for i in range(data_count-1, 0, -1):

ds[i], ds[0] = ds[0], ds[i] # 把最大值放在位置i处

heap_adjust(0, i) # 从0~i-1进行堆调整

frames.append(ds)

return frames

堆排序的性能也比较优秀，完成排序需要51次调整。


依次调用以上常见的4种排序算法，分别保存所有帧和html文件。

waiting_sort_data = Data.create()

for sort_method in [bubble_sort, quick_sort, selection_sort, heap_sort]:

frames = sort_method(waiting_sort_data)

draw_chart(frames, file_name='%s.html' % (sort_method.__name__,))

获取以上完整代码、所有数据文件、结果文件：[完整源码下载](./data/sort.zip)