IndexError：弹出索引超出范围（蟒）

Question

我写以下合并排序代码：

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 

我发送的数组： 一个= [ 12,0,232]

我得到以下输出（不同的迭代），并在最后输出我得到的错误，请帮助我不明白为什么错误在那里谢谢你！：

（1 [12] [0，232]） （1 [0] [232]）

回溯（最近最后调用）： ... \ Sort_Class.py” ，第116行，合并 left = left.pop（1）＃从左边移除第一个元素 IndexError：弹出索引超出范围

Answer 1

代码存在问题，例如在此选择中它们都存在：

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)

Answer 2

我不认为.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)，则a不再是一个名单，但一个数字：

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

将不能工作。您可以用del left[0]或left = left[1:]或简单地result.append(left.pop(0))替换这些，如刚刚发布的答案中所述。：^）固定，揭示了另外一个问题，虽然：您的代码获取陷入无限循环，由于这里的逻辑：

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

如果left[0] > right[0]，那么没有分支，没有任何反应要么left或right和你被困住了。如果你调整这个以在这种情况下添加右分支行为，你的代码似乎工作：

>>> 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