算法导论,一章二小节 ,分治算法
python 2f.py
[5, 2, 7, 4, 1, 3, 2, 6]
[1, 2, 2, 3, 4, 5, 6, 7]
分享些细节：算法并不难，但确实写了很久，调试让我很郁闷。
直到写了 def Debugging 目测：
在 python 中当
arr = [1,2,3,4] 我希望能取出 [2,3] 是 arr[1:3] 是最后一位不计算在内的
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
结果输出》》
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
看 每层 对数组的 数组下标取值 ：
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]
本文转自博客园刘凯毅的博客，原文链接：跟我一起学 - 算法导论 - 分治算法，如需转载请自行联系原博主。
