Skip to main content
 首页 » 编程设计

python之合并排序递归错误

2025年02月15日12java哥

我在 python 中编写了这个合并排序代码。当我单独调用函数合并时它运行良好,它对两个不同的排序列表进行排序。但是当我在真正的合并排序递归问题中使用它时,它没有按照预期进行工作。我正在上传我的代码,请帮助我解决这个问题

def merge(list,p,q,r): 
 
    list1=[] 
    list2=[] 
    list3=[] 
    i=0 
    j=0 
    for a in list[:q+1]: 
        list1.append(a) 
    list1.append(99999999999) 
 
    for b in list[q+1:]: 
        list2.append(b) 
    list2.append(9999999999999999999999999) 
    for k in range(len(list)): 
        if list1[i]<list2[j]: 
            list3.insert(k,list1[i]) 
            i=i+1 
        else: 
            list3.insert(k,list2[j]) 
            j=j+1 
        return list3 
 
 
 
 
def mergesort(list,p,r): 
 
    if p<r: 
 
      q=(p+r)/2 
      mergesort(list,p,q) 
      mergesort(list,q+1,r) 
      merge(list,p,q,r) 
 
 
list=[1,5,7,8,2,4,6,9] 
 
mergesort(list,0,7) 
 
print list 

没有故意错误

输出是:

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

它的打印和列表一样 不整理

请您参考如下方法:

您没有在函数“merge”中修改列表

你要么需要修改 list 要么 return new list ,你什么都不做

您可以从合并函数中返回 list3 并将合并排序修改为:

def mergesort(list,p,r): 
    if p<r: 
      q=(p+r)/2 
      mergesort(list,p,q) 
      mergesort(list,q+1,r) 
      list =merge(list,p,q,r) 

嗨让它工作: 使用

 def merge(list,p,q,r): 
 
    list1=[] 
    list2=[] 
    list3=[] 
    i=0 
    j=0 
    for a in list[:q+1]: 
        list1.append(a) 
    list1.append(99999999999) 
 
    for b in list[q+1:]: 
        list2.append(b) 
    list2.append(9999999999999999999999999) 
    for k in range(len(list)): 
        if list1[i]<list2[j]: 
            list3.insert(k,list1[i]) 
            i=i+1 
        else: 
            list3.insert(k,list2[j]) 
            j=j+1 
    return list3 
 
 
 
 
def mergesort(list,p,r): 
 
    if p<r: 
 
      q=(p+r)/2 
      mergesort(list,p,q) 
      mergesort(list,q+1,r) 
      list = merge(list,p,q,r) 
      return list 
 
list=[1,5,7,8,2,4,6,9] 
 
list = mergesort(list,0,7) 
 
print list