Python-归并排序困难

Question

我试图实现合并排序，这是我的代码：

def mergeSort(array):
    result=[]
    n=len(array)
    if n==1:
        result=array
    else:
        a=round(n/2)
        first=mergeSort(array[0:a])
        second=mergeSort(array[a:n])

        for i in range(len(first)):
            for j in range(len(second)):
                if first[i]<second[j]:
                    result.append(first[i])
                    i=i+1
                else:
                    result.append(second[j])
                    j=j+1
    return result

a=[5,4,1,8,7,6,2,3]
b=mergeSort(a)
print(b)

不幸的是，结果是[1]。我的功能有什么问题？

Answer 1

很多事情...

首先，这是一个递归函数，这意味着您不能像此处那样在函数内创建列表：

result=[]

这只会在每次递归调用后重置您的列表，从而扭曲您的结果。最简单的做法是更改作为参数传递给合并排序的列表。

您的下一个问题是您在 for 循环中有一个 for 循环。这是行不通的，因为当第一个 for 循环遍历 first 时，第二个 for 循环将针对 i 的每个增量遍历 second，这不是您想要的。您需要做的是比较 first 和 second 并提取最小值，然后提取下一个最小值，依此类推，直到获得排序列表。因此，您的 for 循环需要更改为以下内容：

while i < len(first) and j < len(second):

这导致我在你的代码中遇到最后一个问题。 while 循环将在满足其中一个条件后退出，这意味着 i 或 j（一个或另一个）将不会达到 len(first) 或 len(second)。换句话说，first 或 second 中都会有一个值未被计算在内。您需要将这个未计算的值添加到您的排序列表中，这意味着您必须在函数末尾实现这个最终摘录：

remaining = first if i < j else second
r = i if remaining == first else j

while r < len(remaining):
    array[k] = remaining[r]
    r = r + 1 
    k = k + 1

这里r表示前面while循环中断的索引值。然后 while 循环将遍历其余的剩余值；将它们添加到排序列表的末尾。

您的合并排序现在应该如下所示：

def mergeSort(array):
    if len(array)==1:
        return array
    else:
        a=round(len(array)/2)
        first=mergeSort(array[:a])
        second=mergeSort(array[a:])
        i = 0
        j = 0
        k = 0
        while i < len(first) and j < len(second):
            if first[i]<second[j]:
                array[k] = first[i]
                i=i+1
                k=k+1
            else:
                array[k] = second[j]
                j=j+1
                k=k+1

        remaining = first if i < j else second
        r = i if remaining == first else j

        while r < len(remaining):
            array[k] = remaining[r]
            r += 1; k += 1

    return array

为了让您更容易理解，我尽量不改动您的代码。但是，如果您仍然难以理解我所做的事情，请尝试使用多个 print 语句调试合并排序，以便您可以跟踪函数的进度并查看哪里出了问题。

Python-归并排序困难

Python-Merge sort difficulties

python

mergesort