python - 使用合并排序功能时获取列表索引超出范围错误

Question

我收到 List index out of range 错误。我也使用了 GeeksforGeeks 程序作为引用，但仍然出现该错误。当我在 Merge_Sort() 函数中不使用它运行它时，我没有得到任何错误。

def Merge(arr, p, q, r):
    n1 = q-p+1
    n2 = r-q
    L = [0]*n1
    M = [0]*n2

    for i in range(0, n1):
        L[i] = arr[p+i-1]
    for j in range(0, n2):
        M[j] = arr[q+j]
    i = 0
    j = 0
    for k in range(r-1):
        if L[i] <= M[j]:
            arr[k] = L[i]
            i = i+1
        else:
            arr[k] = M[j]
        j = j+1

def Merge_Sort(arr, p, r):
    if p < r:
        q = int((p+r)/2)
        Merge_Sort(arr, p, q)
        Merge_Sort(arr, q+1, r)
        Merge(arr, p, q, r)

ar = [5, 3, 6, 1, 2, 9, 7, 8]
n = len(ar)
Merge_Sort(ar, 1, n)
print(ar)

Error:
 line 14, in Merge
    if L[i]<=M[j]:

IndexError: list index out of range

Answer 1

代码不正确:索引值和切片边界有些困惑，还有其他错误:

• 数组索引在 python 中从 0 开始，因此您应该调用 Merge_sort(ar, 0, n)

• 切片长度n1差一，应该是n1 = q - p

• 递归测试应该计算切片长度并且只递归至少有 2 个元素的切片。

• 合并循环不正确:您应该测试 i 和 j 是否都在切片内。一个有效的方法是用这个测试代替比较:

  if i < n1 and (j == n2 or L[i] <= M[j]):
  

• 合并循环应该迭代 k 从 p 到 r 排除，而不是从 0排除r

• j的自增代码错位，应该再缩进一格

考虑第一个索引被包含而第二个被排除要简单得多。网络上有太多坚持其他约定的各种语言的教程，总是让新手程序员感到困惑。

这是一个更正和简化的版本:

def Merge(arr, p, q, r):
    n1 = q - p
    n2 = r - q
    L = arr[p : q]
    M = arr[q : r]
    i = 0
    j = 0
    for k in range(p, r):
        if i < n1 and (j == n2 or L[i] <= M[j]):
            arr[k] = L[i]
            i = i + 1
        else:
            arr[k] = M[j]
            j = j + 1

def Merge_Sort(arr, p, r):
    if r - p >= 2:
        q = (p + r) // 2
        Merge_Sort(arr, p, q)
        Merge_Sort(arr, q, r)
        Merge(arr, p, q, r)

ar = [5, 3, 6, 1, 2, 9, 7, 8]
Merge_Sort(ar, 0, len(ar))
print(ar)

请注意，如果确保左切片始终至少与右切片一样大，则可以使用单个临时数组进一步简化 MergeSort 函数:

def Merge(arr, p, q, r):
    tmp = arr[p : q]
    i = 0
    n = q - p
    while i < n:
        if q == r or tmp[i] <= arr[q]:
            arr[p] = tmp[i]
            i += 1
            p += 1
        else:
            arr[p] = arr[q]
            q += 1
            p += 1

def Merge_Sort(arr, p, r):
    if r - p >= 2:
        q = (p + r + 1) // 2
        Merge_Sort(arr, p, q)
        Merge_Sort(arr, q, r)
        Merge(arr, p, q, r)

ar = [5, 3, 6, 1, 2, 9, 7, 8]
Merge_Sort(ar, 0, len(ar))
print(ar)