Skynet

---------- ---------- 我的新 blog : liukaiyi.cublog.cn ---------- ----------

  BlogJava :: 首页 :: 联系 :: 聚合  :: 管理
  112 Posts :: 1 Stories :: 49 Comments :: 0 Trackbacks

看第二节  - 递归树方法 :
突发奇想 能否 使用 txt 构造出 递归过程 
还是有 上此提到的 递归方法 分治排序



 

# encoding: utf-8  
arr=[]
def printTree():
    ac 
= []
    ii 
= 0 
    
for r in arr :
        c,ss,cc 
= r 
        sc 
= [' ' for i in xrange(cc*(c-1))]
        
for i in xrange(len(sc)) :
            
if i % cc == 0 : sc[i]="" 
        
#print "ci %s ii %s = %s "%(ci,ii,ii < ci)
        if ii>=c  : 
            sc 
= "".join(sc)+"├─"+ss+'  '
        
else :
            sc 
= "".join(sc)+"└─"+ss
        ii 
= c
        ac.append( sc )
        
    
for r in ac[::-1] :
        
print r
    

def MERGE(A,p,q,r):
    
#print "%s:%s - %s:%s" % (p,q+1,q+1,r+1)
    if p==q : L = [A[p],10**10]
    
else : L = A[p:q+1]+[10**10]

    
if q+1==r : R = [A[r],10**10]
    
else : R = A[q+1:r+1]+[10*10]

    i 
= j = 0
    
for k in xrange(p,r+1):
        
if L[i]<R[j] :
            A[k]
=L[i]
            i
+=1
        
else:
            A[k]
=R[j]
            j
+=1
    
# print "%s:%s = %s \n%s:%s = %s\n\n%s" % ( p,q, L , q+1,r,R, A)


def MERGE_SORT(A,p,r,c=1):
    
if p<r:
        q 
= (p+r)/2
        MERGE_SORT(A,p,q,c
+1)
        MERGE_SORT(A,q
+1,r,c+1)
        arr.append( (c,
"%s - %s" % ( A[p:q+1],A[q+1:r+1]) , 3 ) )
        
# Debugging(A,p,q,r, sc )
        MERGE(A,p,q,r)

A
=[5,2,7,4,1,3,2,6]
MERGE_SORT(A,0,len(A)
-1)
print A
printTree() 




输出 (重下往上看  输出 排序过程 ,我就不多说了 应该很好理解了!!):
[1, 2, 2, 3, 4, 5, 6, 7]
├─[2, 4, 5, 7] - [1, 2, 3, 6]
│  ├─[1, 3] - [2, 6]
│  │  ├─[2] - [6]
│  │  └─[1] - [3]
│  ├─[2, 5] - [4, 7]
│  │  ├─[7] - [4]
│  │  └─[5] - [2]






整理 www.blogjava.net/Good-Game
posted on 2009-11-25 23:09 刘凯毅 阅读(1232) 评论(0)  编辑  收藏 所属分类: python算法/函数

只有注册用户登录后才能发表评论。


网站导航: