在python中实现合并排序时得到错误的答案

库南

对于此合并排序实现中的特定输入数组,我得到了错误的答案。

我在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,您会看到一个调用msb变成列表[3, 0, 0],第二个调用将变成列表[4, 100, 0]换句话说,您丢失了信息。这是因为merge总是初始化k=lb

恕我直言,您不应该尝试以这种方式使用全局列表执行合并排序。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章