Python 3 中的递归

Question

我试图以不同的方式进行合并排序（而不是文本中可用的那些......），现在我有一个成功的合并算法，但问题是当我递归调用半列表时，合并的东西没有t 得到更新。帮助我处理递归中的可变生命。

下面给出的代码的输出是： -

[9, 5]

After merging [5, 9]

[12, 4]

After merging [4, 12]

[9, 5, 12, 4] #it should be (the updated one i.e  [5, 9, 4, 12])

After merging [5, 9, 12, 4]

[6, 8]

After merging [6, 8]

[45, 2]

After merging [2, 45]

[6, 8, 45, 2]

After merging [6, 8, 45, 2]

[9, 5, 12, 4, 6, 8, 45, 2]

After merging [4, 5, 6, 8, 9, 12, 45, 2]

[9, 5, 12, 4, 6, 8, 45, 2]

def merge(arr1, arr2):

"""

Input is two sorted lists

Output is a single merged list

"""

        for i in arr1:

            for j in list(range(len(arr2))):

                if i<arr2[j]:

                    arr2.append(arr2[-1])

                    for count in list(range(len(arr2)-1, j, -1)):

                        arr2[count] = arr2[count-1]

                    arr2[j] = i

                    break

                if j == len(arr2)-1:

                    arr2.append(i)

        return arr2

    def mergeSort(arr):

        if len(arr) !=1:

            mergeSort(arr[:len(arr)//2])

            mergeSort(arr[len(arr)//2:])

            print(arr)

            arr = merge(arr[:len(arr)//2],arr[len(arr)//2:])

            print("After merging", arr)

        else:

            return arr

    a = [9,5,12, 4, 6, 8,45, 2]

    mergeSort(a)

    print(a)

Answer 1

我只做了很小的改变，所以代码仍然是你的努力，你是如此接近，看看：问题是，在查看您的代码后，您必须将两半传递给合并方法，并检查它是否为空。此外，返回结果而不是进行原地更改要好得多-def merge(arr1, arr2):&nbsp; &nbsp; &nbsp; &nbsp; for i in arr1:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for j in list(range(len(arr2))):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if i<arr2[j]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; arr2.append(arr2[-1])&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for count in list(range(len(arr2)-1, j, -1)):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; arr2[count] = arr2[count-1]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; arr2[j] = i&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if j == len(arr2)-1:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; arr2.append(i)&nbsp; &nbsp; &nbsp; &nbsp; return arr2def mergeSort(arr):&nbsp; &nbsp; if len(arr) !=1 and len(arr):&nbsp; &nbsp; &nbsp; &nbsp; ary1 = mergeSort(arr[:len(arr)//2])&nbsp; &nbsp; &nbsp; &nbsp; ary2 = mergeSort(arr[len(arr)//2:])&nbsp; &nbsp; &nbsp; &nbsp; print(arr)&nbsp; &nbsp; &nbsp; &nbsp; ary3 = merge(ary1,ary2)&nbsp; &nbsp; &nbsp; &nbsp; print("After merging", ary3)&nbsp; &nbsp; &nbsp; &nbsp; return ary3&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; return arra = [9,5,12, 4, 6, 8,45, 2]print(mergeSort(a))输出[9, 5]After merging [5, 9][12, 4]After merging [4, 12][9, 5, 12, 4]After merging [4, 5, 9, 12][6, 8]After merging [6, 8][45, 2]After merging [2, 45][6, 8, 45, 2]After merging [2, 6, 8, 45][9, 5, 12, 4, 6, 8, 45, 2]After merging [2, 4, 5, 6, 8, 9, 12, 45][2, 4, 5, 6, 8, 9, 12, 45]

Answer 2

你应该mergeSort返回合并的列表，调用者应该输出返回值mergeSort：def merge(arr1, arr2):&nbsp; &nbsp; merged = []&nbsp; &nbsp; while arr1 and arr2:&nbsp; &nbsp; &nbsp; &nbsp; if arr1[0] > arr2[0]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; arr1, arr2 = arr2, arr1&nbsp; &nbsp; &nbsp; &nbsp; merged.append(arr1.pop(0))&nbsp; &nbsp; merged.extend(arr1 or arr2)&nbsp; &nbsp; return mergeddef mergeSort(arr):&nbsp; &nbsp; if len(arr) <= 1:&nbsp; &nbsp; &nbsp; &nbsp; return arr&nbsp; &nbsp; return merge(mergeSort(arr[:len(arr)//2]), mergeSort(arr[len(arr)//2:]))a = [9, 5, 12, 4, 6, 8, 45, 2]print(mergeSort(a))