为什么列表的后半部分在合并排序的递归调用中被注意操作

Question

我接到了一项任务，要在 python 中实现归并排序。我已经编写了代码，但我被困在为什么代码在递归调用后不打印列表的 part_b 以及我该如何修复它。

下面是代码

def merge_sort(list_sort):
    """splits the list in two parts until each part is left with one member"""

    if len(list_sort) ==  1:
        print len(list_sort)
        return list_sort

    if len(list_sort)>= 2:
        x= len(list_sort) / 2
        part_a = list_sort[:x]
        part_b = list_sort[x:]
        print part_a , part_b
        merge_sort(part_a)
        merge_sort(part_b)

    return merge(part_a, part_b)


def merge(left , right):
    """merges the two parts of list after sorting them"""
    print left, right 
    sorted_list = []
    if len(left) >= len(right):
        i = len(left)
        while i != 0:
            if left[i] > right[i]:
                sorted_list.append(right[i])
            else :
                sorted_list.append(left[i])
            i = i-1
        sorted_list += right[i:]
    else :
        i = len(right)
        while i != 0:
            if left[i] > right[i]:
                sorted_list.append(right[i])
            else :
                sorted_list.append(left[i])
            i = i-1
        sorted_list += left[i:]
    return sorted_list

details = [3, 7, 5, 12, 14, 11, 2, 6]
print merge_sort(details)

Answer 1

您正在尝试使用您的 merge_sort 就好像它在适当的位置运行一样，但它没有。您需要捕获它的 return 值：

part_a = merge_sort(part_a)
part_b = merge_sort(part_b)

Answer 2

您的 merge_sort 函数 returns 排序列表，但在您调用它的两个位置都丢弃了结果。您需要分配结果（将其绑定到一个名称），以便您可以将这些结果传递给 merge:

if len(list_sort) >= 2:
    x= len(list_sort) / 2
    part_a = list_sort[:x]
    part_b = list_sort[x:]
    print part_a , part_b
    sorted_part_a = merge_sort(part_a)
    sorted_part_b = merge_sort(part_b)
    return merge(sorted_part_a, sorted_part_b)

Answer 3

我认为您的说法不正确。我更新了你的 prints 以标记输出

    print "SORT A", part_a , "\tB", part_b

print "MERGE left", left, "\tright", right

并得到了预期的跟踪，直到它在合并阶段因索引处理不当而崩溃。正如其他人指出的那样，这是由于未能从 merge.

中保存 return 值

SORT A [3, 7, 5, 12]    B [14, 11, 2, 6]
SORT A [3, 7]   B [5, 12]
SORT A [3]  B [7]
1
1
MERGE left [3]  right [7]
Traceback (most recent call last):
  File "so.py", line 44, in <module>
    print merge_sort(details)
  File "so.py", line 13, in merge_sort
    merge_sort(part_a)
  File "so.py", line 13, in merge_sort
    merge_sort(part_a)
  File "so.py", line 16, in merge_sort
    return merge(part_a, part_b)
  File "so.py", line 26, in merge
    if left[i] > right[i]:
IndexError: list index out of range

根据 OP 评论更新

由于您的（有效）调用顺序，B 部分未被操作：算法必须先完成 A 部分的排序和合并，然后才能处理 B 部分。由于索引范围错误，您无法做到这一点.您在尝试合并 [3] 和 [7] 时犯了错误——分别是 AAA 和 AAB 部分。您从未备份堆栈（AA 和 AB）来处理原始部分 B。

为什么列表的后半部分在合并排序的递归调用中被注意操作

Why the second half of list is note operated on in a recursive call in merge sort

python

mergesort