defbubbleSort(a): for i in range(len(a)): for j in range(len(a)-i-1): if (a[j] > a[j+1]): a[j], a[j+1] = a[j+1], a[j]
插入排序
definsertSort(a): for i in range(len(a)): min = i for j in range(i+1, len(a)): if a[min] > a[j]: min = j a[i], a[min] = a[min], a[i]
希尔排序(升级版插入排序)
defshellSort(a): gap = len(a)//2 while gap > 0: for i in range(gap, len(a)): j = i current = a[i] while j - gap >= 0and current < a[j-gap]: a[j] = a[j-gap] j -= gap a[j] = current gap //= 2
快速排序
defquickSort(a): if len(a) < 2: return a else: pivot = a[0] less = [i for i in a[1:] if i <= pivot] greater = [i for i in a[1:] if i > pivot] return quickSort(less) + [pivot] + quickSort(greater)
a = quickSort(a)
绘制的逻辑
要做到自己绘制每一帧,我们需要按照这样的逻辑来执行:
flowchart TB subgraph 排序过程 擦除上一帧的画面--"plt.cla()"--->绘制当前的散点--"plt.scatter(x,y,s,c)"--->暂停一个时长--"进入新的周期"-->擦除上一帧的画面 end 暂停一个时长--排序结束后-->a["plt.show()<br>plt.close()"]
那么代码就很简单了:
plt.cla() x = range(0, 100) plt.scatter(a, x, color="00", s=2) plt.pause(0.01)
将这段代码放置到能体现排序算法特点的循环周期内,在循环结束依次后展示所有的画面:
plt.show() plt.close()
至此,可视化过程就已经实现了。
后记
完整代码示例
import random import matplotlib.pyplot as plt
definitList(): a = list(range(100)) a = random.sample(a, k=100) return a
defdraw_frame(a): plt.cla() x = list(range(100)) plt.scatter(x, a, color="00", s=2) plt.pause(0.01)
defbubbleSort(a): for i in range(len(a)-1): for j in range(len(a)-i-1): if a[j] > a[j+1]: a[j], a[j+1] = a[j+1], a[j] draw_frame(a)
defpartition(a, low, high): draw_frame(a) i = (low-1) pivot = a[high]
for j in range(low, high): if a[j] <= pivot:
i = i+1 a[i], a[j] = a[j], a[i]
a[i+1], a[high] = a[high], a[i+1]
return (i+1)
defquickSort(a, low, high): if low < high:
pi = partition(a, low, high)
quickSort(a, low, pi-1) quickSort(a, pi+1, high)
definsertSort(a): for i in range(len(a)): min = i for j in range(i+1, len(a)): if a[min] > a[j]: min = j a[i], a[min] = a[min], a[i] draw_frame(a)
defshellSort(a): gap = len(a)//2 while gap > 0: for i in range(gap, len(a)): j = i current = a[i] while j - gap >= 0and current < a[j-gap]: a[j] = a[j-gap] j -= gap a[j] = current draw_frame(a) gap //= 2
import random import matplotlib.pyplot as plt import copy import matplotlib.animation as animation
classmethod: name = ""
definit_list(self): a = list(range(-100, 100)) a = random.sample(a, k=len(a)) return a
defbubble_sort(self, data, store): a = copy.deepcopy(data) for i in range(len(a)-1): for j in range(len(a)-i-1): if a[j] > a[j+1]: a[j], a[j+1] = a[j+1], a[j] c = copy.deepcopy(a) store.append(c)
defshell_sort(self, data, store): gap = len(data)//2 while gap > 0: for i in range(gap, len(data)): j = i current = data[i] while j - gap >= 0and current < data[j-gap]: data[j] = data[j-gap] j -= gap data[j] = current c = copy.deepcopy(data) store.append(c) gap //= 2
definsert_sort(self, data, store): for i in range(len(data)): min_pos = i for j in range(i+1, len(data)): if data[min_pos] > data[j]: min_pos = j data[i], data[min_pos] = data[min_pos], data[i] c = copy.deepcopy(data) store.append(c)
defpartition(self, a, low, high): c = copy.deepcopy(a) store.append(c) i = (low-1) pivot = a[high]
for j in range(low, high): if a[j] <= pivot: i = i+1 a[i], a[j] = a[j], a[i]
a[i+1], a[high] = a[high], a[i+1]
return (i+1)
defquick_sort(self, data, low, high, store):
if low < high: pi = self.partition(data, low, high) self.quick_sort(data, low, pi-1, store) self.quick_sort(data, pi+1, high, store)
defmaking_animation(self, name, store): self.name = name fig = plt.figure(num=1, dpi=100) fig.add_subplot(1, 1, 1) ani = animation.FuncAnimation( fig, self.update_frames, interval=80, blit=False, repeat=False, frames=int(len(store))) ani.save('%s.gif' % name, writer="ffmpeg", progress_callback=lambda i, n: print(name+"Processing"+str(int(i/n*100))+"%")) fig.clf() store = [] return store
if __name__ == '__main__':
methods = method() store = [] a = methods.init_list() data = copy.deepcopy(a)
methods.bubble_sort(data, store) store = methods.making_animation("BubbleSort", store)
data = copy.deepcopy(a) methods.quick_sort(data, 0, len(data)-1, store) store = methods.making_animation("QuickSort", store)
data = copy.deepcopy(a) methods.shell_sort(data, store) store = methods.making_animation("ShellSort", store)
data = copy.deepcopy(a) methods.insert_sort(data, store) store = methods.making_animation("InsertSort", store)
简单修改一下图形绘制模式,把散点图修改为柱状图,可以很容易得到柱状图形式的排序动画:
import random import matplotlib.pyplot as plt import copy import matplotlib.animation as animation
classmethod: name = "" mark = []
definit_list(self): a = list(range(0, 100)) a = random.sample(a, k=len(a)) return a
defbubble_sort(self, data, store): a = copy.deepcopy(data) for i in range(len(a)-1): for j in range(len(a)-i-1): if a[j] > a[j+1]: a[j], a[j+1] = a[j+1], a[j] self.mark.append(j) c = copy.deepcopy(a) store.append(c)
defshell_sort(self, data, store): gap = len(data)//2 while gap > 0: for i in range(gap, len(data)): j = i current = data[i] while j - gap >= 0and current < data[j-gap]: data[j] = data[j-gap] j -= gap data[j] = current self.mark.append(j) c = copy.deepcopy(data) store.append(c)
gap //= 2
definsert_sort(self, data, store): for i in range(len(data)): min_pos = i for j in range(i+1, len(data)): if data[min_pos] > data[j]: min_pos = j self.mark.append(j) data[i], data[min_pos] = data[min_pos], data[i] c = copy.deepcopy(data) store.append(c)
defpartition(self, a, low, high): c = copy.deepcopy(a) store.append(c) i = (low-1) pivot = a[high]
for j in range(low, high): if a[j] <= pivot: i = i+1 a[i], a[j] = a[j], a[i] self.mark.append(j) a[i+1], a[high] = a[high], a[i+1]
return (i+1)
defquick_sort(self, data, low, high, store):
if low < high: pi = self.partition(data, low, high) self.quick_sort(data, low, pi-1, store) self.quick_sort(data, pi+1, high, store)