为什么我不能以这种方式实现合并排序

Question

我理解mergesort通过分而治之的方式工作，你保持一半，直到你达到一个你可以在恒定时间排序的点，或者列表只是一个lement然后你合并列表。

def mergesort(l):
    if len(l)<=1:
        return l
    l1 = l[0:len(l)//2+1]
    l2 = l[len(l)//2:]

    l1 = mergesort(l1)
    l2 = mergesort(l2)

    return merge(l1,l2)

我有一个工作合并实现，我检查它工作正常但合并排序实现不起作用它只返回列表的一半元素。

我在互联网上看到mergesort是使用l＆r和m =（l + r）/ 2实现的。我的实施有什么问题？我递归地细分列表并合并。

Answer 1

您列出的代码似乎没有进行任何排序。我无法确定，因为你没有列出merge（）函数的代码，但上面函数唯一能做的就是递归地将列表分成两半。这是一个合并排序的工作实现：

def mergeSort(L):

    # lists with only one value already sorted
    if len(L) > 1:
        # determine halves of list
        mid = len(L) // 2
        left = L[:mid]
        right = L[mid:]

        # recursive function calls
        mergeSort(left)
        mergeSort(right)

        # keeps track of current index in left half
        i = 0
        # keeps track of current index in right half
        j = 0
        # keeps track of current index in new merged list
        k = 0

        while i < len(left) and j < len(right):
            # lower values appended to merged list first
            if left[i] < right[j]:
                L[k] = left[i]
                i += 1
            else:
                L[k] = right[j]
                j += 1
            k += 1

        # catch remaining values in left and right
        while i < len(left):
            L[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            L[k] = right[j]
            j += 1
            k += 1
    return L

您的函数不会比较原始列表中的值。此外，当您将列表分成两半时：

l1 = l[0:len(l)//2 + 1]

'+ 1'是不必要的（实际上可能会导致错误的解决方案）。你可以简单地使用：

l1 = l[:len(l)//2]

如果长度是偶数（即12），它将从[0：6]和[6:12]分成两半。如果它是奇数，它仍将自动正确分割（即长度= 13将是[0：6]和[6:13]。我希望这有帮助！

Answer 2

问题是代码中的+1，这里：

l1 = l[0:len(l)//2]
l2 = l[len(l)//2:]

用你的代码替换它，你就没事了