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

Question

我理解合并排序的工作原理是分而治之，你一直减半，直到达到可以在恒定时间内排序的点，或者列表只是一个元素，然后你合并列表。

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)

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

我在网上看到合并排序是使用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] 分成两半。如果它是奇数，它仍然会自动正确划分（即 length = 13 将是 [0:6] 和 [6:13]。我希望这有帮助！

Answer 2

问题出在您代码中的 +1，此处：

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

用您的代码替换它就可以了

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

Why can't I implement merge sort this way

python

sorting

algorithm

merge

mergesort