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