0

我编写了以下合并排序代码:

def merge_sort(self,a):

    #console.log(len(a))
    if len(a) <= 1:
        return a
    left = []
    right = []
    result = []
    middle = int(len(a)/2)
    print middle

    left = a[:middle] #set left equal to the first half of a
    right = a[middle:] #set right equal to the second half of a
    print left
    print right

    left = self.merge_sort(left)
    right = self.merge_sort(right)
    result = self.merge(left, right)

    return result

然后合并代码:

def merge(self, left, right):
    result = []
    while len(left) > 0 or len(right) > 0:

        if len(left) > 0 and len(right) > 0:
            if left[0] <= right[0]:
                result.append(left[0])
                left = left.pop(1)    #remove the first element from left

        elif len(left) > 0:
            result.append(left[0])
            left = left.pop(1)    #remove the first element from left

        elif len(right) > 0:
            result.append(right[0])
            right = right.pop(1)  #remove the first element from right

        else:
            result.append(right[0])
            right = right.pop(1)
    return result

我将数组发送给它:a = [12,0,232]

我得到以下输出(不同的迭代),在最后一个输出中我得到了错误,请帮助我不明白为什么会出现错误,谢谢!:

(1 [12] [0, 232]) (1 [0] [232])

Traceback (last recent call last): ...\Sort_Class.py", line 116, in merge left = left.pop(1) #remove the first element from left IndexError: pop index out of range

4

2 回答 2

3

您的代码存在问题,例如在此选择中它们都存在:

result.append(left[0])
left = left.pop(1)

这应该是:

result.append(left.pop(0))

问题是:

  1. Python列表使用基于0的索引,因此列表left[0]的第一个元素不会弹出第一个元素而弹出第二个元素left[1]left.pop(0)left.pop(1)
  2. left.pop(1)返回弹出的元素而不是列表,因为它会改变列表。left = left.pop(1)在这里没有多大意义。
  3. 不需要同时获取第一个元素left[0]然后弹出它left.pop(0)
于 2012-10-15T01:17:32.237 回答
0

我不认为.pop()你认为它会做。例如,这一行:

left = left.pop(1)    #remove the first element from left

不会从中删除“第一个”(即第零个)元素left.pop(1)是第二个元素:

>>> a = [10,20,30,40]
>>> a.pop(1)
20
>>> a
[10, 30, 40]

而且,如果你设置a = a.pop(1), thena不再是一个列表,而是一个数字:

>>> a = [10,20,30,40]
>>> a = a.pop(1)
>>> a
20

这也行不通。您可以将这些替换为del left[0]orleft = left[1:]或简单地result.append(left.pop(0))按照刚刚发布的答案中的说明进行替换。:^) 修复它揭示了另一个问题:由于这里的逻辑,您的代码陷入了无限循环:

    if len(left) > 0 and len(right) > 0:
        if left[0] <= right[0]:

如果left[0] > right[0],则没有分支,或者 没有任何反应leftright你就被困住了。如果您对此进行调整以添加右分支行为,您的代码似乎可以工作:

>>> import random
>>> def check():
...     for length in range(1, 10):
...         for trial in range(10000):
...             v = [random.randrange(-10, 10) for i in range(length)]
...             assert merge_sort(v) == sorted(v)
...     return True
... 
>>> check()
True
于 2012-10-15T01:20:36.920 回答