我了解合并排序是如何工作的，但是當我試圖用python實作時，我想我還是有點困惑，到底堆棧上的事情是如何工作的。我有一個名為merge_sorted_list的函數，用于合并兩個已排序的清單，還有一個名為merge_sort1和merge_sort2的函數，用于遞歸過程。”merge_sort1“和“merge_sort2”非常相似，但隻有merge_sort2給出了正确的答案。看起來merge\u sort1沒有在堆棧的每個級别上擷取傳回值。有誰能告訴我merge\u sort1和merge\u sort2在評估上有什麼差別嗎？在def merge_sorted_list(list1,list2):
if(len(list1) == 0 or len(list2) == 0):
print('input error')
return;
i = 0
j = 0
k = 0
list_merge = [0]*(len(list1) + len(list2))
while(i < len(list1) and j < len(list2)):
if (list1[i] < list2[j]):
list_merge[k] = list1[i]
i += 1
else:
list_merge[k] = list2[j]
j += 1
k += 1
while(i < len(list1)):
list_merge[k] = list1[i]
i += 1
k += 1
while (j < len(list2)):
list_merge[k] = list2[j]
j += 1
k += 1
return(list_merge)
def merge_sort1(mylist):
print("splitting ",mylist)
if (len(mylist) > 1):
mid = len(mylist)//2
merge_sort1(mylist[:mid])
merge_sort1(mylist[mid:])
# lefthalf = mylist[:mid]
# righthalf = mylist[mid:]
# merge_sort1(lefthalf)
# merge_sort1(righthalf)
mylist[:] = merge_sorted_list(mylist[:mid],mylist[mid:])
print("merging result ",mylist)
return mylist
def merge_sort2(mylist):
print("splitting ",mylist)
if (len(mylist) > 1):
mid = len(mylist)//2
# merge_sort2(mylist[:mid])
# merge_sort2(mylist[mid:])
lefthalf = mylist[:mid]
righthalf = mylist[mid:]
merge_sort2(lefthalf)
merge_sort2(righthalf)
mylist[:] = merge_sorted_list(lefthalf,righthalf)
print("merging result ",mylist)
return mylist
如果我們嘗試merge\u sort1([4,67,3,3,2,6])，輸出将是
^{pr2}$
merge_sort2([4,67,3,3,2,6])的輸出将是('splitting ', [4, 67, 3, 3, 2, 6])
('splitting ', [4, 67, 3])
('splitting ', [4])
('splitting ', [67, 3])
('splitting ', [67])
('splitting ', [3])
('merging result ', [3, 67])
('merging result ', [3, 4, 67])
('splitting ', [3, 2, 6])
('splitting ', [3])
('splitting ', [2, 6])
('splitting ', [2])
('splitting ', [6])
('merging result ', [2, 6])
('merging result ', [2, 3, 6])
('merging result ', [2, 3, 3, 4, 6, 67])
非常感謝