我正在学习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
根据我的逻辑,一旦我到达函数的末尾,因为没有循环,我应该退出函数,但(正如它应该的)其他两个值 也被分析和分类。
1条答案
按热度按时间deikduxw1#
代码看起来运行良好。由于MergeSort正在修改原始列表,因此不需要
return list
。然而(应该是)另外两个值 也被分析和分类
代码看起来运行良好。由于MergeSort正在修改原始列表,因此不需要
return list
。然而(应该是这样),其他两个值也被分析和排序
函数MergeSort调用自身两次:
顺序为深度优先,左侧优先。只有在只有2个元素要合并时才会进行合并:左[44]中1,右[16]中1,合并生成[16,44]。然后返回调用MergeSort(right),以获取[83,7],合并生成[7,83]。然后返回上一级嵌套,将[16,44]与[7,83]合并。显示操作顺序: