python 算法合并排序,因为在划分列表并排序前两个值之后,在我的例子中,16和44,为什么再次执行该函数?

31moq8wy  于 2023-01-16  发布在  Python
关注(0)|答案(1)|浏览(101)

我正在学习python中合并排序算法背后的逻辑。在划分列表并对前两个值进行排序之后 在我的例子16和44中,为什么再次执行函数?
这是密码:

def MergeSort(list):
    if len(list)>1:
        mid = len(list)//2 #splits list in half
        left = list[:mid]
        right = list[mid:]

        MergeSort(left) #repeats until length of each list is 1
        MergeSort(right)

        a = 0
        b = 0
        c = 0
        while a < len(left) and b < len(right):
            if left[a] < right[b]:
                list[c]=left[a]
                a = a + 1
            else:
                list[c]=right[b]
                b = b + 1
            c = c + 1
        while a < len(left):
            list[c]=left[a]
            a = a + 1
            c = c + 1

        while b < len(right):
            list[c]=right[b]
            b = b + 1
            c = c + 1
    return list

根据我的逻辑,一旦我到达函数的末尾,因为没有循环,我应该退出函数,但(正如它应该的)其他两个值 也被分析和分类。

deikduxw

deikduxw1#

代码看起来运行良好。由于MergeSort正在修改原始列表,因此不需要return list
然而(应该是)另外两个值 也被分析和分类
代码看起来运行良好。由于MergeSort正在修改原始列表,因此不需要return list
然而(应该是这样),其他两个值也被分析和排序
函数MergeSort调用自身两次:

MergeSort(left)
        MergeSort(right)

顺序为深度优先,左侧优先。只有在只有2个元素要合并时才会进行合并:左[44]中1,右[16]中1,合并生成[16,44]。然后返回调用MergeSort(right),以获取[83,7],合并生成[7,83]。然后返回上一级嵌套,将[16,44]与[7,83]合并。显示操作顺序:

44 16 83  7
44 16
44
   16
16 44
      83  7
      83
          7
       7 83
 7 16 44 83

相关问题