时间戳

首页 > 解决方案 > 在python中实现归并排序

python - 在python中实现归并排序

问题描述

我正在尝试在 Python 3 中实现合并排序算法。这是实现算法合并部分的函数：

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

#We first populate two lists that contain the sorted subsequences A[p,...,q] and A[q+1,...,r]
L = []
R = []

for index in range(n1):
    L.append(A[index + p])

for index in range(n2):
    R.append(A[index + q + 1])

#We now overwrite the A[p,..,q,...r] section of the list by comparing the 'top-most'
#elements in the lists l and R and putting the smaller element in the corresponding
#entry in A. If one of the list is fully exposed/no longer available, we simply put the 
#remaining list's elements in the corresponding positions in A.

i = 0
j = 0

for k in range(r - p + 1 ):

    if i > n1-1:
        A[k] = R[j]
        j = j + 1

    elif j > n2-1:
        A[k] = L[i]
        i = i + 1

    elif L[i] < R[j]:
        A[k] = L[i]
        i = i + 1

    else:
        A[k] = R[j]
        j = j + 1 

return A

我已经测试过这个函数并且它运行良好：只要子数组 A[p,q] 和 A[q+1,r] 被排序，整个数组 A[p,r] 就会被正确排序。我现在尝试实施一种分而治之的方法来合并足够大的列表。

import math

def Merge_Sort(A,p,r):

if p == r:

    return A

if p < r:

    q = math.floor((p+r)/2)
    Merge_Sort(A,p,q)
    Merge_Sort(A,q+1,r)
    Merged_List = Merge(A,p,q,r)

return Merged_List

但是当我运行它时，我得到了错误的答案。这是一个例子：

#We now analyze the merge sort algorithm.
A = [1,7,9,3]
B = Merge_Sort(A,0,3)
print(B)

输出是

[3, 9, 3, 9]

在实现分而治之的过程中，我可能犯了一些明显/愚蠢的错误。建议？

标签： python

解决方案

错误出现在对 的分配中A[k]。它们应更改为分配给A[p+k].

请注意，LandR可以使用以下语法定义（无显式循环）：

L = A[p:q+1]
R = A[q+1:r+1]

为了与 Python 中原生函数的工作方式保持一致（例如list.extend），您的两个函数不应返回列表。它们会改变您作为参数传递的列表，因此为避免混淆，最好不要返回它：它可能使您的代码用户认为该函数没有副作用。

推荐阅读