def merge(arr,l,m,h):
lis = []
l1 = arr[l:m]
l2 = arr[m 1:h]
while((len(l1) and len(l2)) is not 0):
if l1[0]<=l2[0]:
x = l1.pop(0)
else:
x = l2.pop(0)
lis.append(x)
return lis
def merge_sort(arr,l,h): generating them
if l<h:
mid = (l h)//2
merge_sort(arr,l,mid)
merge_sort(arr,mid 1,h)
arr = merge(arr,l,mid,h)
return arr
arr = [9,3,7,5,6,4,8,2]
print(merge_sort(arr,0,7))
誰能告訴我我的方法哪里出錯了？我只得到 [6,4,8] 作為答案。我試圖理解演算法并以自己的方式實作邏輯。請幫忙。
uj5u.com熱心網友回復：
幾個問題：
當您認為
h是子串列的最后一個索引時，請意識到在對串列進行切片時，第二個索引是預期范圍之后的索引。所以改變這個：錯誤的 對 l1 = arr[l:m]l1 = arr[l:m 1]l2 = arr[m 1:h]l2 = arr[m 1:h 1]作為
merge回傳子串列的結果，您不應將其分配給arr.arr應該是總串列，所以你應該只替換它的一部分：arr[l:h 1] = merge(arr,l,mid,h)由于
while回圈需要兩個串列不是空的，你還是應該考慮這樣的情況后，串列的一環仍沒有空：它的元素應該被添加到合并結果。所以將return陳述句替換為：return lis l1 l2不建議將整數與
isor進行比較is not，您在這種while情況下會這樣做。事實上，這個條件可以簡化為：while l1 and l2:
通過這些更改（和正確的縮進），它將起作用。
補充說明：
這種實作效率不高。pop(0)時間復雜度為 O(n)。使用您在回圈期間更新的索引，而不是真正從串列中提取值。
leth和m成為它們關閉的范圍之后的索引更加pythonic ，而不是它們是它們關閉的范圍內最后一個元素的索引。所以如果你走那條路，那么上面的一些問題將得到不同的解決。
更正的實施
這是使用上述所有注釋改編的代碼：
def merge(arr, l, m, h):
lis = []
i = l
j = m
while i < m and j < h:
if arr[i] <= arr[j]:
x = arr[i]
i = 1
else:
x = arr[j]
j = 1
lis.append(x)
return lis arr[i:m] arr[j:h]
def merge_sort(arr, l, h):
if l < h - 1:
mid = (l h) // 2
merge_sort(arr, l, mid)
merge_sort(arr, mid, h)
arr[l:h] = merge(arr, l, mid, h)
return arr
arr = [9, 3, 7, 5, 6, 4, 8, 2]
print(merge_sort(arr,0,len(arr)))
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/405602.html
標籤：