为什么在 Python 中使用 Mergesort 时 return 值为 0？

Question

我正在编写合并排序代码，但它没有排序。你看到它有什么问题了吗？

def mergeSort(L):
   if len(L) == 1:
       return L
   else:
       # divide
       L1 = mergeSort(L[0:round(len(L)/2)])
       L2 = mergeSort(L[round(len(L)/2):len(L)])
    
       # merge
       i = 0
       j = 0
       K = []
       while i < len(L1) and j < len(L2):
           if L1[i] < L2[j]:
               K.append(L1[i])
               i=i+1
           else:
               K.append(L2[j])
               j=j+1
       return K

输入：

L = [1,2,5,7,8,0,10,21,32,53,16,16,48,59,64,53,75,52,42,21,98,76‌]

输出：

L = [0]

Answer 1

while i < len(L1) and j < len(L2):

我觉得这不对。在这种情况下，一旦 i 或 j 到达各自列表的末尾，循环就会结束。因此，另一个列表中可能仍有元素永远不会被迭代。

尝试将 and 更改为 or，并添加一些检查以确保仅在两个列表都尚未完全迭代时才进行列表间比较：

    while i < len(L1) or j < len(L2):
        if i < len(L1) and (j == len(L2) or L1[i] < L2[j]):
            K.append(L1[i])
            i=i+1
        else:
            K.append(L2[j])
            j=j+1

现在你的代码输出 [0, 1, 2, 5, 7, 8, 10, 16, 16, 21, 21, 32, 42, 48, 52, 53, 53, 59, 64, 75, 76, 98].

Answer 2

考虑这一行：

while i < len(L1) and j < len(L2):

例如，如果L1中的所有元素都小于L2中的所有元素，则此循环会将L1中的所有元素放入结果[=15] =].然后循环将结束，所有 L2 将被忽略 。当此循环结束时，您需要清理剩余的元素。在循环之后立即添加这行代码：

K.extend(L1[i:] + L2[j:])

顺便说一句，我是通过使用调试器逐步执行您的代码并输入 L=[2,1] 来发现这一点的。我发现当我只通过 while 循环进行一次迭代时，由于每次循环迭代都添加了一个元素，因此结果中只能有一个元素。如果您还不知道如何使用调试器单步执行代码，现在是学习的好时机。

Answer 3

在 while 条件下，“与”操作应该已更改为“或”，然后您的问题就解决了。

def merge_sort(L):
    if len(L) == 1:
        return L

    else:
        # divide
        L1 = merge_sort(L[0:round(len(L) / 2)])
        L2 = merge_sort(L[round(len(L) / 2):len(L)])

        # merge
        i = 0
        j = 0
        K = []
        while i < len(L1) or j < len(L2):
            if i < len(L1) and (j == len(L2) or L1[i] < L2[j]):
                K.append(L1[i])
                i = i + 1
            else:
                K.append(L2[j])
                j = j + 1
        return K

现在您将获得所需的输出，并且不会显示为零。

为什么在 Python 中使用 Mergesort 时 return 值为 0？

Why return value is 0 when use Mergesort in Python?

python

sorting

merge

mergesort

python-3.x