从伪代码 Python 实现归并排序遇到问题

Question

从伪代码 Python 实现归并排序遇到问题

3

我正在尝试根据以下伪代码在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

- Luka Jozić

1

你可以使用 float('inf') 表示正无穷，使用 float('-inf') 表示负无穷。 - M-Chen-3

3个回答

1

这是一个使用“现代”约定的算法重写，其中包括以下内容：

索引从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

- Walter Tross

非常感谢您。我很喜欢您的版本，但不幸的是，我需要尽可能接近伪代码。 - Luka Jozić

如果你按照我上一行所示的方式计算q，那么这段代码将完全像你提供的伪代码一样移动数据，因此在我看来，它是尽可能接近的。在Python中，你不能使用基于1的索引，除非进行可怕而痛苦的黑客攻击，对于list切片和range()的范围结束也是如此。 - Walter Tross

1

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

数组的区域[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值，我将当前处理的数组区域分成了两个较小的区域。
在代码的第4行，对区域[i, mid)调用了MergeSort函数，在第5行，对区域[mid, j)调用了MergeSort函数。

您可以通过这里访问整个代码。

- Aman Godara

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Eloy Pérez Torres · Accepted Answer

首先，您需要确保由 p 和 r 表示的间隔在其端点处是开放还是关闭的。伪代码（for循环包括最后一个索引）确定该间隔在两个端点都关闭：[ p，r ]。
在考虑最后一个观察结果时，您可以注意到for k in range（p，r）：不检查最后一个数字，因此正确的行是 for k in range（p，r +1）：。您可以通过在范围[ p，r ]中使用 A 的最大元素加一来表示“无穷大”。这将完成工作。您不需要返回数组 A ，因为所有更改都是通过其引用完成的。另外， q =（p +（r-1））// 2 不是错误的（因为p q =（p + r）// 2 ，因为您想要两个数字的中间整数值的间隔。