两句闲话
本文所说的排序是指基于交换的排序。因此，按理来说，本文应该叫基于交换的排序的动态展示，但是这样太拗口了。
效果展示
最终效果如下。
实现方法
需要说明的是，在这里是通过pygame来实现图形界面；程序使用python 3.5编写。使用pygame的好处在于，它非常自由（当然也非常麻烦）。
我们一共需要编写四个文件：draw.py，sort_show.py，sort.py，main.py。
1.draw.py
在这里，我们先在draw.py中写一个Draw类，以实现pygame生成界面的基本流程。需要说明的是，这个类中有一些东西，在这里我们并不会用到。
# -*- coding: utf-8 -*-
"""
Created on Tue Dec 29 10:24:50 2015
@author: super zhang
"""
import pygame
from pygame.locals import *
class Draw:
"""
to provide a general structure for using pygame
STRUCTURE:
self.mainloop()
|-self.run_init()
| |-self.S_pre_run_init()
| |-self.S_update()
|
|-self.run()
|-sef.S_event(event)
| |-self.S_keydown_event(key)
| |-self.S_keyup_event(key)
| |-self.S_mousebutton_event(button)
|
|-self.S_mouse_move_event()
|-self.S_time()
|-self.S_move()
|-self.S_update()
|-self.S_draw()
|-self.S_load_img()
METHOD:
self.M_screen_mode(mode,SCREEN_SIZE)
self.M_draw_text(size,text,pos,text_color)
self.M_mouse_pos()
self.M_load_img(img_file)
"""
def __init__(self):
self.SCREEN_SIZE=(720,480)
self.screen_mode=0
def M_screen_mode(self,mode,SCREEN_SIZE):
"""usually called in __init__"""
self.screen_mode=mode
self.SCREEN_SIZE=SCREEN_SIZE
def mainloop(self):
self.run_init()
while True:
self.run()
def run_init(self):
pygame.init()
self.S_pre_run_init()
self.screen=pygame.display.set_mode(self.SCREEN_SIZE,self.screen_mode,32)
self.S_update()
def S_pre_run_init(self):
pass
def run(self):
for event in pygame.event.get():
if event.type==QUIT:
pygame.quit()
else:
self.S_event(event)
self.S_mouse_move_event()
self.S_time()
self.S_move()
self.S_update()
def S_event(self,event):
if event.type==KEYDOWN:
self.S_keydown_event(event.key)
elif event.type==KEYUP:
self.S_keyup_event(event.key)
elif event.type==MOUSEBUTTONDOWN:
self.S_mousebutton_event(event.button)
def S_keydown_event(self,key):
pass
def S_keyup_event(self,key):
pass
def S_mousebutton_event(self,button):
pass
def S_mouse_move_event(self):
pass
def S_time(self):
pass
def S_move(self):
pass
def S_update(self):
self.screen.fill((0,0,0))
self.S_draw()
self.S_load_img()
pygame.display.update()
def S_load_img(self):
pass
def S_draw(self):
pass
def M_draw_text(self,size,text,pos,text_color):
#for further use
cur_font=pygame.font.SysFont("宋体",size)
text_fmt=cur_font.render(text,1,text_color)
self.screen.blit(text_fmt,pos)
def M_mouse_pos(self):
return pygame.mouse.get_pos()
def M_load_img(self,img_file):
return pygame.image.load(img_file)
if __name__=="__main__":
d=Draw()
d.mainloop()
2.sort_show.py
下面是动态展示排序的主类，写在sort_show.py中
import pygame
from pygame.locals import *
from draw import Draw
class SortShow(Draw):
def __init__(self,lst,lst_change):
Draw.__init__(self)
self.lst=lst
self.lst_change=lst_change
self.len=len(lst)
self.max=max(lst)
self.step=0
self.whole_step=len(lst_change)
self.time_delay=100#ms
self.stop_flag=True
def S_draw(self):
pygame.time.delay(self.time_delay)
self._change_lst()
self._cal_rect()
self._draw_rect()
self._put_text()
def _change_lst(self):
if not self.stop_flag:
if self.step<self.whole_step:
changing=self.lst_change[self.step]
i=changing[0]
j=changing[1]
flag=changing[2]
if flag==1:
self.lst[i],self.lst[j]=self.lst[j],self.lst[i]
if flag==2:
key=self.lst[j]
del self.lst[j]
self.lst[i+1:i+1]=[key]#move key
self.step=self.step+1
def _cal_rect(self):
self.rects=[]
x_div=720.0/self.len
y_div=480.0/self.max/1.5
for i in range(self.len):
width=x_div-1
height=self.lst[i]*y_div
length=i*x_div
top=480-height
rect=[length,top,width,height]
self.rects+=[rect]
changing=self.lst_change[self.step-1]
p1=changing[0]
p2=changing[1]
for i in [p1,p2]:
width=x_div-1
height=self.lst[i]*y_div
length=i*x_div
top=480-height
rect=[length,top,width,height]
self.rects+=[rect]
def _draw_rect(self):
for rect in self.rects[:-2]:
pygame.draw.rect(self.screen,(255,255,255),rect,0)
#rect: left,top,width,height
if self.step<self.whole_step:
for rect in self.rects[-2:]:
pygame.draw.rect(self.screen,(0,0,255),rect,0)
def _put_text(self):
self.M_draw_text(20,"1.press esc to quit",(20,20),(0xff,0xff,0x0))
self.M_draw_text(20,"2.press T to set delay_time",(20,40),(0xff,0xff,0x0))
self.M_draw_text(20,"3.press s to start or stop",(20,60),(0xff,0xff,0x0))
def S_keydown_event(self,key):
if key==K_ESCAPE:
exit()
if key==K_t:
self._set_time_delay()
if key==K_s:
self.stop_flag=not(self.stop_flag)
def _set_time_delay(self):
try:
print ("-*-delay_time set-*-")
time_delay=int(input("please input delay time
defalut vlaue is 100ms
time(ms):"))
self.time_delay=time_delay
finally:
print ("-*-finish-*-")
3.sort.py
接下来，我们在sort.py中写冒泡排序（也可以写其他排序），这里的排序要输出每次交换的两个元素的下标
import random
def ge(min_value,max_value):
def tmp(num):
lst=[]
for i in range(num):
value=random.randint(min_value,max_value)
lst.append(value)
return lst
return tmp
def bubble_sort(lst):
lst1=lst[:]
res=[]
num=len(lst1)
for i in range(num-1):#from 1 to num
for j in range(num-1,i,-1):#from num-1 to i+1
tmp=[j-1,j,0]
if lst1[j-1]>lst1[j]:
lst1[j-1],lst1[j]=lst1[j],lst1[j-1]
tmp[2]=1
res.append(tmp)
return res
if __name__=="__main__":
lst=ge(0,999)(100)
changing=bubble_sort(lst)
print (changing)
4.main.py
最后在main.py中，调用sort.py和sort_show.py
import sort import sort_show lst=sort.ge(0,999)(100) changing=sort.bubble_sort(lst) s=sort_show.SortShow(lst,changing) s.mainloop()
运行main.py就能得到文章开始的效果了。