python 自底向上的归并排序
``````def MERGE(A, p, q, r):
s=p
t=q+1
B=[]
while s<=q and t<=r:
if A[s]<=A[t]:
B.append(A[s])
s=s+1
else:
B.append(A[t])
t=t+1
if s==q+1:
while t<=r:
B.append(A[t])
t=t+1
else:
while s<=q:
B.append(A[s])
s=s+1
A=B
print(A)

A=[8,7,6,5,4,3,2,1]
t=1
n=8
print('原数组是：',A)
while t<n:
s=t
t=2*s
i=0
while i+t<=n:
MERGE(A, i, i+s-1, i+t-1)
i=i+t
print(A)
if i+s<n:
MERGE(A, i, i+s-1, n-1)
print('排序后的数组是：',A)
``````

[7, 8]
[8, 7, 6, 5, 4, 3, 2, 1]
[5, 6]
[8, 7, 6, 5, 4, 3, 2, 1]
[3, 4]
[8, 7, 6, 5, 4, 3, 2, 1]
[1, 2]
[8, 7, 6, 5, 4, 3, 2, 1]
[6, 5, 8, 7]
[8, 7, 6, 5, 4, 3, 2, 1]
[2, 1, 4, 3]
[8, 7, 6, 5, 4, 3, 2, 1]
[4, 3, 2, 1, 8, 7, 6, 5]
[8, 7, 6, 5, 4, 3, 2, 1]

1个回答

``````import copy
def MERGE(A, p, q, r):
s=p
t=q+1
l=len(A)
B=[]
for j in range(0,s):
B.append(A[j])
while s<=q and t<=r:
if A[s]<=A[t]:
B.append(A[s])
s=s+1
else:
B.append(A[t])
t=t+1
if s==q+1:
while t<=r:
B.append(A[t])
t=t+1
else:
while s<=q:
B.append(A[s])
s=s+1
for i in range(r+1,l):
B.append(A[i])
A[:]=B
#print('B数组是：',B)
#print('A数组是：',A)
return A

C=[8,7,6,5,4,3,2,1]
t=1
n=8
print('原数组是：',C)
while t<n:
s=t
t=2*s
i=0
while i+t<=n:
MERGE(C, i, i+s-1, i+t-1)
i=i+t
if i+s<n:
MERGE(C, i, i+s-1, n-1)
print('排序后的数组是：',C)

``````