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

我应该如何在没有这些代码的情况下，从伪代码转换为Python代码？错误？

Answer 1

有一个小错误--很容易查看这个，索引与您的合并函数一致

Astart +I-1应该是start + i

因为您从0开始循环i，并且开始值也可以得到0，这使得它开始+i -1。

对于迭代，其中

start == i == 0

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

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

for k in range( start，end+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)