Python MergeSort排序不正确

rsaldnfx 于 2023-01-22 发布在 Python

关注(0)|答案(1)|浏览(161)

我正在尝试实现python Merge Sort，但由于某种原因，当合并时，它根本不能正确排序。我正在尝试将伪代码转换为Python代码，但我失败得很惨。如果有人能帮忙，我将非常感激。我已经尝试调试它，但我只是感到困惑。

def mergeSort(A, p, r):
    if p < r:
        q = int(((p + (r-1)) / 2))
        mergeSort(A, p, q)
        mergeSort(A, q + 1, r)
        merge(A, p, q, r)

def merge(A, p, q, r): # Issue with sorting
    n1 = q - p + 1
    n2 = r - q
    L = [0] * n1
    R = [0] * n2
    for i in range(0, n1):
        L[i] = A[p + i]
    for j in range(0, n2):
        R[j] = A[q + j]
    L.append(infinity)
    R.append(infinity)
    i = 0
    j = 0
    for k in range(p,r):
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1

输入示例：
[“日期”、“苹果”、“香蕉”、“ cucumber ”、“橡子”、"aaaaa“]
输出示例：
[“香蕉”、“橡子”、“aaaa”、“ cucumber ”、“日期”、"日期“]
mergeSort psuedocode
merge pseudocode

python-3.x

来源：https://stackoverflow.com/questions/75179779/python-mergesort-not-sorting-correctly

1条答案

按热度按时间

xoshrz7s1#

实现的问题是在将两个子列表合并在一起时没有正确更新索引。

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

你应该增加k而不是i和j。if语句中的条件应该是L[i]〈= R[j]而不是L[i]〉= R[j]。
以下是合并函数的更正版本：

def merge(A, p, q, r):
n1 = q - p + 1
n2 = r - q
L = [0] * n1
R = [0] * n2
for i in range(0, n1):
    L[i] = A[p + i]
for j in range(0, n2):
    R[j] = A[q + j]
i = 0
j = 0
k = p
while i < n1 and j < n2:
    if L[i] <= R[j]:
        A[k] = L[i]
        i += 1
    else:
        A[k] = R[j]
        j += 1
    k += 1
while i < n1:
    A[k] = L[i]
    i += 1
    k += 1
while j < n2:
    A[k] = R[j]
    j += 1
    k += 1

此外，您必须导入数学库，并使用math.inf而不是infinity。

赞(0）回复(0）举报 2023-01-22

我来回答

Python MergeSort排序不正确

1条答案

相关问题

热门标签

最新问答