Python 中的简单合并排序错误

Question

我在 Python 中进行合并排序赋值，但我一直有 RuntimeError: maximum recursion depth exceeded 的错误这是我的代码：

def merge_sort(list):
    left_num = len(list) // 2
    left_sorted = merge_sort(list[:left_num])
    right_sorted = merge_sort(list[left_num:])
    final_sort = merge(left_sorted, right_sorted)
    return final_sort

def merge(left_sorted, right_sorted):
    final_sort = []
    while left_sorted and right_sorted:
        if left_sorted[0] <= right_sorted[0]:
            final_sort.append(left_sorted[0])
            left_sorted.pop(0)
        else:
            final_sort.append(right_sorted[0])
            right_sorted.pop(0)
    final_sort = final_sort + left_sorted + right_sorted
    return final_sort

if __name__ == "__main__":
    list = [4, 2]
    print(merge_sort(list))

谁能告诉我为什么？为了使问题对其他人更有用，请随时编辑问题以使其更有意义。 ^_^

Answer 1

您在 merge_sort 中没有出口点。您需要执行以下操作：

left_num = len(list) // 2
if left_num <= 1:
    return list

你总是需要在递归函数中有条件退出：if COND then EXIT else RECURSION_CALL。

Answer 2

编写递归函数时，应注意基本情况，它决定递归何时结束。

在您的案例中，缺少基本案例。例如，如果列表只有一个元素，那么您就不必再次对它进行递归排序。所以，这是你的基本条件。

def merge_sort(list):
    if len(list) == 1:
        return list
    ...
    ...

注：变量名list隐藏了内置函数list。所以最好避免使用内置名称。

因为你做了很多 pop(0)s，值得注意的是它在列表上效率不高。引用 Python's official documentation,

Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.

所以，更好的选择是使用 collections.deque, instead of list, if you are popping a lot. The actual popping from a deque is done with popleft method.

>>> from collections import deque
>>> d = deque([4, 2])
>>> d.popleft()
4
>>> d
deque([2])

Python 中的简单合并排序错误

Simple Merge Sort bug in Python

python

recursion

mergesort

list

python-3.x