在 python 中执行合并排序算法的变体时索引超出范围？

Question

根据我从 CLRS 书中学到的知识，我在 python 中对合并排序算法做了一个变体，并将其与麻省理工学院介绍性计算机科学书中的实现进行了比较。我在我的算法中找不到问题，并且 IDLE 给了我一个超出范围的索引，尽管我觉得一切都很好。我不确定这是否是由于从麻省理工学院算法中借用思想的一些混乱（见下文）。

lista = [1,2,3,1,1,1,1,6,7,12,2,7,7,67,4,7,9,6,6,3,1,14,4]   

def merge(A, p, q, r):
    q = (p+r)/2
    L = A[p:q+1]
    R = A[q+1:r]

    i = 0
    j = 0

    for k in range(len(A)):

        #if the list R runs of of space and L[i] has nothing to compare
        if i+1 > len(R):
            A[k] = L[i]
            i += 1

        elif j+1 > len(L):
            A[k] = R[j]
            j += 1

        elif L[i] <= R[j]:
            A[k] = L[i]
            i += 1

        elif R[j] <= L[i]:
            A[k] = R[j]
            j += 1

        #when both the sub arrays have run out and all the ifs and elifs done,
        # the for loop has effectively ended

    return A


def mergesort(A, p, r):
    """A is the list, p is the first index and r is the last index for which
        the portion of the list is to be sorted."""
    q = (p+r)/2
    if p<r:
        mergesort(A, p, q)
        mergesort(A, q+1, r)
        merge (A, p, q, r)
    return A

print mergesort(lista, 0, len(lista)-1)

我已经尽可能地遵循了 CLRS 中的伪代码，只是没有使用 L 和 R 末尾的 "infinity value"，这将继续比较（这样效率低吗？）。我试图在麻省理工学院的书中融入这样的想法，即简单地将剩余的 L 或 R 列表复制到 A，以变异 A 和 return 排序列表。但是，我似乎找不到它出了什么问题。另外，我不明白为什么伪代码需要 'q' 作为输入，因为对于中间索引，无论如何 q 都会被计算为 (p+q)/2 。为什么需要放 p

另一方面，从麻省理工学院的书中，我们有一些看起来非常优雅的东西。

def merge(left, right, compare):
    """Assumes left and right are sorted lists and
compare defines an ordering on the elements.
Returns a new sorted(by compare) list containing the
same elements as(left + right) would contain.
"""
    result = []
    i, j = 0, 0

    while i < len(left) and j < len(right):
        if compare(left[i], right[j]):
            result.append(left[i])
            i += 1
        else :
            result.append(right[j])
            j += 1

    while (i < len(left)):
        result.append(left[i])
        i += 1

    while (j < len(right)):
        result.append(right[j])
        j += 1

    return result

import operator

def mergeSort(L, compare = operator.lt):
    """Assumes L is a list, compare defines an ordering
on elements of L. 
Returns a new sorted list containing the same elements as L"""
if len(L) < 2:
    return L[: ]
else :
    middle = len(L) //2
left = mergeSort(L[: middle], compare)
right = mergeSort(L[middle: ], compare)
return merge(left, right, compare)

我哪里可能出错了？

此外，我认为 MIT 实现的主要区别在于它创建了一个新列表而不是改变原始列表。这让我很难理解合并排序，因为我发现 CLRS 的解释非常清楚，通过理解它发生的不同递归层来对原始列表中最微小的组件进行排序（长度为 1 的列表不需要排序），因此 "storing" 旧列表本身的递归结果。

不过，转念一想，MIT算法中每次递归"result"return，依次组合，这样说对吗？

谢谢！

Answer 1

您的代码与 MIT 的根本区别在于合并排序函数中的条件语句。你的 if 语句在哪里：

if p<r:

他们的是：

if len(L) < 2:

这意味着如果您在递归调用树中的任何一点都有一个 len(A) == 1 的列表，那么它仍然会在大小为 1 甚至大小的情况下调用 merge 0 列表。您可以看到这会导致合并函数出现问题，因为这样您的 L、R 或两个子列表的大小最终都可能为 0，这将导致 out if bounds 索引错误。

你的问题可以通过将你的 if 语句更改为与他们类似的语句来轻松解决，例如 len(A) < 2 或 r-p < 2

在 python 中执行合并排序算法的变体时索引超出范围？

Index out of range in implementation of a variation of mergesort algorithm in python?

python

algorithm

sorting

recursion

mergesort