对于此合并排序实现中的特定输入数组,我得到了错误的答案。
我在python中尝试了以下代码。
Python代码-
a=[100,3,4]
b=[]
for i in range(len(a)):
b.append(0)
def ms( a ,lb,ub ):
if (lb<ub):
mid=int((lb+ub)/2)
ms(a, lb, mid)
ms(a, mid+1,ub)
merge(a,lb,mid,ub)
def merge(a,lb,mid,ub):
i=lb
j=mid+1
k=lb
while (i<=mid and j<=ub) :
if a[i]<=a[j]:
b[k]=a[i]
i+=1
k+=1
else:
b[k]=a[j]
j+=1
k+=1
if (i>mid) :
while j<=ub :
b[k]=a[j]
j+=1
k+=1
elif (j>ub) :
while i<=mid :
b[k]=a[i]
i+=1
k+=1
ms(a,0 , len(a)-1)
print(b)
我得到输出错误的答案。请通过这个。
此代码有几个问题。您不需要修复,我可以想象至少有两种方法可以修复它,因此我将其留给您,但是从根本上说,实现中的基本问题是您要合并b
两次,两种次开始。这将覆盖第一个的功能。
如果在ms
调用前添加打印语句merge
,您会看到一个调用ms
将b
变成列表[3, 0, 0]
,第二个调用将变成列表[4, 100, 0]
。换句话说,您丢失了信息。这是因为merge
总是初始化k=lb
。
恕我直言,您不应该尝试以这种方式使用全局列表执行合并排序。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句