从伪代码实现合并排序时出现问题 python

Question

我正在尝试根据以下伪代码在 Python 中实现归并排序。我知道那里有很多实现，但我一直无法找到一个遵循这种模式的实现，它在末尾有一个 for 循环而不是 while 循环。此外，将子数组中的最后一个值设置为无穷大是我在其他实现中从未见过的。注意：以下伪代码具有基于 1 的索引，即索引从 1 开始。所以我认为我最大的问题是正确设置索引。现在它只是没有正确排序并且很难用调试器跟踪。我的实现在底部。

当前输出：

Input:  [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
Merge Sort:  [0, 0, 0, 3, 0, 5, 5, 5, 8, 0]

def merge_sort(arr, p, r):
    if p < r:
        q = (p + (r - 1)) // 2
        merge_sort(arr, p, q)
        merge_sort(arr, q + 1, r)
        merge(arr, p, q, r)

def merge(A, p, q, r):
    n1 = q - p + 1
    n2 = r - q

    L = [0] * (n1 + 1)
    R = [0] * (n2 + 1)

    for i in range(0, n1):
        L[i] = A[p + i]

    for j in range(0, n2):
        R[j] = A[q + 1 + j]

    L[n1] = 10000000 #dont know how to do infinity for integers
    R[n2] = 10000000 #dont know how to do infinity for integers

    i = 0
    j = 0

    for k in range(p, r):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

    return A

Answer 1

首先，您需要确定由 p 和 r 表示的区间在其端点处是开还是闭。伪代码（for loops include last index）确定区间在两个端点都是闭合的：[p, r].

考虑到最后的观察，您可以注意到 for k in range(p, r): 不检查最后一个数字，因此正确的行是 for k in range(p, r + 1):。

您可以通过使用范围 [p, r] 中 A 的最大元素来表示问题中的“无穷大”加上一。这将使工作完成。

您不需要 return 数组 A 因为所有更改都是通过它的引用完成的。

此外，q = (p + (r - 1)) // 2 没有错（因为 p < r）但正确的方程是 q = (p + r) // 2 作为您想要两个数字的中间整数值的间隔。

Answer 2

这里是用“现代”约定重写的算法，如下：

索引从 0 开始
范围的结尾不是该范围的一部分；换句话说，区间在左边是封闭的，在右边是开放的。

这是结果代码：

INF = float('inf')

def merge_sort(A, p=0, r=None):
    if r is None:
        r = len(A)
    if r - p > 1:
        q = (p + r) // 2
        merge_sort(A, p, q)
        merge_sort(A, q, r)
        merge(A, p, q, r)

def merge(A, p, q, r):
    L = A[p:q]; L.append(INF)
    R = A[q:r]; R.append(INF)
    i = 0
    j = 0
    for k in range(p, r):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

A = [433, 17, 585, 699, 942, 483, 235, 736, 629, 609]
merge_sort(A)
print(A)
# → [17, 235, 433, 483, 585, 609, 629, 699, 736, 942]

备注：

Python 有一个方便的复制子范围的语法。
Python 中没有 int 无穷大，但我们可以使用 float 无穷大，因为整数和浮点数总是可以比较的。
这个算法和原来的算法有一处不同，但无关紧要。由于“中点”q 不属于左侧范围，因此当它们的长度之和为奇数时，L 比 R 短。在原来的算法中，q属于L，所以L在这种情况下是两者中较长的一个。这不会改变算法的正确性，因为它只是交换 L 和 R 的角色。如果出于某种原因你需要 而不是 来获得这种差异，那么你必须像这样计算 q：

        q = (p + r + 1) // 2

Answer 3

在数学中，我们用[=64=表示所有大于或等于i且小于j的实数][i,j)。注意这里使用了 [ 和 ) 括号。我在我的代码中以相同的方式使用 i 和 j 来表示我当前正在处理的区域。

Th地区[i, j)一个数组的索引（整数值）覆盖了这个数组的所有大于或等于 i 且小于 j 的索引（整数值）。 i 和 j 是从 0 开始的索引。暂时忽略first_array和second_array。

请注意，i 和 j 定义了我当前正在处理的数组区域。

更好地理解这一点的例子

如果你的区域跨越整个数组，那么i应该是0并且j应该是数组的长度 [0, length).

地区[i,i + 1)其中只有索引 i。

地区[i,i + 2)其中有索引 i 和 i + 1。

def mergeSort(first_array, second_array, i, j):
    if j > i + 1:
        mid = (i + j + 1) // 2
        mergeSort(second_array, first_array, i, mid)
        mergeSort(second_array, first_array, mid, j)
        merge(first_array, second_array, i, mid, j)

可以看到我计算的中点为 mid = (i + j + 1) // 2 或者也可以使用 mid = (i + j) // 2 两者都可以。我将使用这个计算出的 mid 值将我当前正在处理的数组区域划分为 2 个较小的区域。
在代码的 行 4 中， MergeSort 在区域 [i, mid) 并且在 行 5 中，MergeSort 在区域 上被调用[mid, j).

您可以访问整个代码 here。

从伪代码实现合并排序时出现问题 python

Problem implementing Merge Sort from pseudo code python

python

sorting

algorithm

mergesort

更好地理解这一点的例子