CLRS 中的伪代码存在问题

Question

我正在使用CLRS作为算法的介绍。我正在尝试用Python实现书中用伪代码编写的算法。但是，我遇到了问题，因为这本书从 1 开始索引。这就是我实现合并排序的方式，但它无法正常工作：

def MergeSort(A, start, end):
    if(start < end):
        middle = math.floor((start + end)/2)
        MergeSort(A, start, middle)
        MergeSort(A, middle + 1, end)
        Merge(A, start, middle, end)
def Merge(A, start, middle, end):
    n1 = middle - start + 1
    n2 = end - middle
    L = [0] * n1
    R = [0] * n2
    for i in range(0, n1):
        L[i] = A[start + i - 1]
    for j in range(0, n2):
        R[j] = A[middle + j]
    i = 0
    j = 0
    for k in range(start, end):
        if(i >= n1):
            A[k] = R[j]
            j += 1
        elif(j >= n2):
             A[k] = L[i]
             i += 1
        elif(L[i] <= R[j]):
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

我应该如何在没有这些（逐个关闭？

Answer 1

有一个

小错误很容易忽略这个，索引在你的合并函数行

A[开始 + i - 1] 应该是开始 + i

因为你从 0 开始循环 i，并且 start 的值也可以得到 0，这使得它开始 + i -1
对于迭代，其中

开始 == i == 0

你的索引变成 -1，这实际上是 Python 中列表的最后一个元素

并在合并函数的最后一个循环中 范围应为

对于范围内的 k（开始，结束+1），因为它必须从启动到结束（包括）进行迭代

这应该运行良好

import math
def MergeSort(A, start, end):
    if(start < end):
        middle = math.floor((start + end)/2)
        MergeSort(A, start, middle)
        MergeSort(A, middle + 1, end)
        Merge(A, start, middle, end)
def Merge(A, start, middle, end):
    n1 = middle - start + 1
    n2 = end - middle
    L = [0] * n1
    R = [0] * n2
    for i in range(0, n1):
        L[i] = A[start + i ]
    for j in range(0, n2):
        R[j] = A[middle + j+1]
    i = 0
    j = 0
    for k in range(start, end+1):
        if(i >= n1):
            A[k] = R[j]
            j += 1
        elif(j >= n2):
             A[k] = L[i]
             i += 1
        elif(L[i] <= R[j]):
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

arr=[4,8,5,6,9,8,1]
MergeSort(arr,0,len(arr)-1)
print(arr)