2

我是 python 新手，正在尝试在 Python 中实现 merge_sort，这是我的代码。但它进入无限循环。谁能指出为什么？谢谢

def merge_sort(a):
    '''implement merge sort for array'''
    l = len(a)
    if l == 1:
        return a[0]
    a1 = merge_sort(a[:l/2-1])
    a2 = merge_sort(a[l/2:-1])
    a_sort = []
    idx1, idx2 = 0, 0
    #for i in range(l):
    if idx1 == len(a1):
        a_sort.append(a2[idx2:])
        import ipdb; ipdb.set_trace()
        return a_sort
    elif idx2 == len(a2):
        a_sort.append(a1[idx1:])
        return a_sort
    else:      
        if a1[idx1] >= a2[idx2]:
            a_sort.append(a2[idx2])
            idx2 += 1
        else:
            a_sort.append(a1[idx1])
            idx1 += 1
4

3 回答 3

0

问题是当您的递归下降到一个空列表（即l == 0）时，您在返回任何内容之前调用merge_sort([])了两次。您需要添加一个检查if l == 0: return [].

另外，您的检查if l == 1: return a[0]有点错误；merge_sort应该总是返回一个列表，而这会返回一个列表元素（数字或字符串或其他）。所以它可能应该只是

if l <= 1:
    return a

另外，您a2实际上不包括数组的最后一个元素：您想要a[l/2:]，而不是a[l/2:-1]. （请记住，Python 中的范围不包括最后一个元素。）

这不会影响代码的正确性，但您应该使用l // 2to 表示整数除法；在 Python3 中，或者如果你这样做，如果是奇数from __future__ import division，l/2将是一个浮点数。l

于 2012-04-15T06:37:28.980 回答
0

谢谢！工作代码如下

def merge_sort(a):
'''implement merge sort for array'''
l = len(a)
if l == 1:
    return a
a1 = merge_sort(a[:l//2])
a2 = merge_sort(a[l//2:])
a_sort = []
idx1, idx2 = 0, 0
while idx1 < len(a1) and idx2 < len(a2):
    if a1[idx1] >= a2[idx2]:
        a_sort.append(a2[idx2])
        idx2 += 1
    else:
        a_sort.append(a1[idx1])
        idx1 += 1
if idx1 < len(a1):
    a_sort.extend(a1[idx1:])
else:
    a_sort.extend(a2[idx2:])
return a_sort
于 2012-04-15T17:04:47.580 回答
0

正如 Dougal 和 Andrei 所指出的，无限循环是由未经检查的边缘条件引起的。if l == 1:用/替换行if l < 2:。
代码中还有其他问题：

  • alist by position的左部和右部l/2是对应的a[:l/2]和a[l/2:]。不需要减1。只要认为一个位置在两个项目之间。
  • 在and分支中使用.extend()而不是append()ifelif
  • 不要忘记将注释掉的 forloop 取回。
  • 终于没有return了

而且通常while结构更方便

while idx1 < len(a1) and idx2 < len(a2):
    'code in your else branch'    
if idx1 < len(a1):
    a_sort.extend(a1[idx1:])
else:
    a_sort.extend(a2[idx2:])
return a_sort
于 2012-04-15T07:37:06.013 回答