算法導論,一章二小節 ,分治算法
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 Debugging(A,p,q,r,c):
print "%s\t%s:%s - %s:%s" % (c,p,q,q+1,r)
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)
#Debugging(A,p,q,r,c)
MERGE(A,p,q,r)
A=[5,2,7,4,1,3,2,6]
print A
MERGE_SORT(A,0,len(A)-1)
print A
結果輸出》》
python 2f.py
[5, 2, 7, 4, 1, 3, 2, 6]
[1, 2, 2, 3, 4, 5, 6, 7]
分享些細節：算法并不難，但確實寫了很久，調試讓我很郁悶。
直到寫了 def
Debugging 目測：
python 2f.py
3 0:0 - 1:1
3 2:2 - 3:3
2 0:1 - 2:3
3 4:4 - 5:5
3 6:6 - 7:7
2 4:5 - 6:7
1 0:3 - 4:7
看 每層 對數組的 數組下標取值 ：
在 python 中當
arr = [1,2,3,4] 我希望能取出 [2,3] 是 arr[1:3] 是最后一位不計算在內的
最典型的 arr[0,1] == [1]
整理 m.tkk7.com/Good-Game