-1

这是我用于合并排序的 Python 代码，我不明白为什么我得到了IndexError第 23 行。

如果将第 23 行放在for循环之前但在for循环中它说list index out of range. :(

from math import floor

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

def merge(A,p,q,r):
 n1 = q - r +1
 n2 = r - q
 L = []
 R = []
 #print n1
 for i in range (1,n1):
  L.append(a[p+i-1])
 for j in range (1,n2):
  R.append(a[q+j])
 L.append(10000)
 R.append(10000)
 i,j=0,0

 for k in range (p,r):
  if L[i] <= R [j]: # This is where the error occurs
   A[k] = L[i]
   i = i + 1
  else :  
   A[k] = R[j]
   j = j + 1



a=[1,4,9,8,2,3,8,2,9]
merge_sort(a,1,len(a)) 
print a
4

2 回答 2

0

我同意评论者/其他海报，这个脚本有一个 Python 语法（除了不是习惯的 4 个空格的缩进......），但远非Pythonic......

无论如何，对于您的问题：看起来问题出现在mergewhen (p,q,r)=(1,2,3)。在这种情况下，n1=0和n2=1。循环range(1,n1)不会给你任何东西，因此你L将只有 1 个元素（10000你在循环之外附加到它）。

现在，当您到达for k in range (p,r)循环时：

  • 在第一次迭代中，k=p=1，L[0] <= R[0]你添加1到i，所以i=1
  • 在第二次迭代中，您尝试访问未定义的L[i]ie 。L[1]因此，IndexError.

一些建议：

  • 了解如何使用调试器。许多 IDE 都带有一些实现，这确实很有帮助。
  • 请记住，列表从索引 0 开始。当您来自另一种语言时，您往往会忘记这一点。
于 2012-08-25T10:53:53.360 回答
0

这不是 python，这是带有 Python 语法的 Pascal。

这是合并排序算法的实现（基于合并排序维基文章）：

def merge_sort(data):
    if len(data) <= 1:
        return data

    middle = len(data) / 2

    left = merge_sort(data[0:middle])
    right = merge_sort(data[middle:])

    return merge(left, right)


def merge(left, right):
    result = []

    while left or right:
        if left and right:
            if left[0] <= right[0]:
                result.append(left.pop(0))
                continue

            result.append(right.pop(0))
            continue

        if left:
            result.append(left.pop(0))
        elif right:
            result.append(right.pop(0))

    return result


data = [1, 4, 9, 8, 2, 3, 8, 2, 9]
result = merge_sort(data)

assert len(data) == len(result)

print result
于 2012-08-25T09:52:50.647 回答