超出范围错误 - 归并排序算法

Question

我正在尝试使用以下代码实现合并排序算法，但出现列表索引超出范围错误。

def mergeSort (unSortedList):
if len(unSortedList) == 1 :
    return unSortedList
else:
    midpoint = len(unSortedList)//2
    A = mergeSort (unSortedList[:midpoint] )
    B = mergeSort (unSortedList[midpoint:] )
    i = 0
    j = 0
    C = []
    for k in range(len(unSortedList)):
        if A[i] >= B[j]:
            C.append(A[i])
            if i == len(A):
                C.append(B[j:])
            else:
                i += 1
        elif A[i] < B[j] :
            C.append(B[j])
            if j == len(B):
                C.append(A[i:])
            else:
                j += 1
    return C
testlist = [2,1,4,2,5,6,8,9]
print (mergeSort(testlist))

如有任何帮助，我们将不胜感激。

Answer 1

这是我的 mergeSort 版本，提取了 merge 函数：

def mergeSort (unSortedList):
    if len(unSortedList) == 1 :
        return unSortedList
    else:
        midpoint = len(unSortedList)//2
        A = mergeSort (unSortedList[:midpoint] )
        B = mergeSort (unSortedList[midpoint:] )
        return merge(A, B)

def merge(a, b):
    i = 0
    j = 0
    c = []
    while True:
        if a[i] < b[j]:
            c.append(b[j])
            j += 1
        elif a[i] >= b[j]:
            c.append(a[i])
            i += 1

        if i == len(a):
            c.extend(b[j:])
            break
        if j == len(b):
            c.extend(a[i:])
            break
    return c

输出：

>>> testlist = [2,1,4,2,5,6,8,9]
>>> mergeSort(testlist)
[9, 8, 6, 5, 4, 2, 2, 1]

有两点需要注意：

将列表附加到列表。 当您执行 C.append(A[j:]) 时，您最终会得到嵌套列表。那是因为 A[j:] 总是 returns 一个列表。您需要使用列表添加 - C += A[j:] - 或调用 extend - C.extend(A[j:])
缺少中断。 当您的 i 或 j 到达他们列表的末尾时，您正确地附加了另一个列表的其余部分，但您确实这样做了不终止循环。这就是导致范围错误的原因，因为在下一次迭代中（这不应该发生）您试图在索引处获取一个项目，该项目等于超出范围的列表的长度。

超出范围错误 - 归并排序算法

Out of range error - merge sort algorithm

mergesort

python-2.7