递归调用合并排序算法

Question

我是递归的新手,目前正在编写一个Merge Sort算法,它比较两个列表的第一个元素并确定哪一个更小,然后将较小的一个添加到新列表中.

我正在尝试在每次比较后更新三个列表并让函数再次使用更新的列表调用自己,但是我在Pycharm中得到了未解决的引用问题而不确定我做错了什么.到目前为止,这是我的代码,我想要的输出是:

new_list = [4,8,15,16,23,42,50,75,108]

def merge_Sort(list1, list2, new_list):
    list1 = [8, 15, 16, 50, 75]
    list2 = [4, 23, 42, 108]
    new_list = []
    for i in range(len(list1)):
            if list1[0] < list2[0]:
                new_list = new_list.append(list1[0])
                list1 = list1.remove(list1[0])
                break


            elif list1[0] > list2[0]:
                new_list = new_list.append(list2[0])
                list2 = list2.remove(list2[0])
                break

    merge_Sort(list1, list2, new_list)

merge_Sort(list1, list2, new_list)

Answer 1

您的代码会导致无限递归.你应该移动list1,list2并new_list在merge_Sort函数之外进行初始化.

def merge_Sort(list1, list2, new_list):
    for i in range(len(list1)):
        if list1[0] < list2[0]:
            new_list.append(list1[0])
            list1.remove(list1[0])
            break
        elif list1[0] > list2[0]:
            new_list.append(list2[0])
            list2.remove(list2[0])
            break

    merge_Sort(list1, list2, new_list)

list1 = [8, 15, 16, 50, 75]
list2 = [4, 23, 42, 108]
new_list = []
merge_Sort(list1, list2, new_list)