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

有一个小错误，很容易忽略这个，索引符合您的合并功能

A[start + i - 1] 应该是 start + i

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

开始==我== 0

您的索引变为 -1，这实际上是 Python

中列表的最后一个元素

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

for k in range(start, end+1) 因为它必须从开始迭代到结束 inclusive

这应该运行很好

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)

CLRS 中伪代码的问题

Problems with the pseudocode in CLRS

python

sorting

algorithm

mergesort