我有一個關于 Python 版本的遞歸合并排序的問題。我完成了基本版本，僅由數組引用，現在正在研究索引版本。我會陷入無限循環，卻又不知道自己哪里做錯了。您介意分享一些想法嗎？先感謝您。成功和非索引版本：def mergesort(x): # The base case is when the array contains less than 1 observation. length = len(x) if length < 2: return x else: # Recursive case:merge sort on the lower subarray, and the upper subarray. mid = (length) // 2 lower = mergesort(x[:mid]) upper = mergesort(x[mid:]) # merge two subarrays. x_sorted = merge(lower, upper) return (x_sorted)def merge(lower, upper): nlower = len(lower) nupper = len(upper) i, j, k = 0, 0, 0 # create a temp array to store the sorted results temp = [0] * (nlower + nupper) # as the lower and upper are sorted, since the base case is the single observation. # now we compare the smallest element in each sorted array, and store the smaller one to the temp array # repeat this process until one array is completed moved to the temp array # store the other array to the end of the temp array while i < nlower and j < nupper: if lower[i] <= upper[j]: temp[k] = lower[i] i += 1 k += 1 else: temp[k] = upper[j] j += 1 k += 1 if i == nlower: temp[i+j:] = upper[j:] else: temp[i+j:] = lower[i:] return temp 預期結果：x = random.sample(range(0, 30), 15)mergesort(x)[0, 1, 3, 6, 9, 10, 11, 13, 14, 17, 18, 20, 25, 27, 29]但我會陷入索引版本的無限循環：def ms(x, left, right): # the base case: right == left as a single-element array if left < right: mid = (left + right) // 2 ms(x, left, mid) ms(x, mid, right + 1) m(x, left, mid, right) return mdef m(x, left, mid, right): nlower = mid - left nupper = right - mid + 1 temp = [0] * (nlower + nupper) ilower, iupper, k = left, mid, 0
1 回答
斯蒂芬大帝
TA貢獻1827條經驗 獲得超8個贊
您的索引版本使用了令人困惑的約定，其中left是切片中第一個元素的索引，right也是最后一個元素的索引。這個約定需要容易出錯+1/-1調整。你的問題是這樣的：mid計算出來的是左半部分最后一個元素的索引，但你認為它mid是右半部分的第一個元素：2個元素的切片被分成一個帶有0的元素和一個帶有2的元素，因此無限遞歸。您可以通過更改ms(x, mid, right+1)為ms(x, mid+1, right)等來解決此問題。
此外，m從功能中恢復ms是沒有意義的。x如果有什么的話你應該回來。
right將索引設置為最后一個元素之后的索引更不容易出錯，就像 Python 中的范圍說明符一樣。這樣就不會有混亂+1/-1調整。
這是修改后的版本：
def ms(x, left, right):
# the base case: right - left as a single-element array
if right - left >= 2:
mid = (left + right) // 2 # index of the first element of the right half
ms(x, left, mid)
ms(x, mid, right)
m(x, left, mid, right)
return x
def m(x, left, mid, right):
nlower = mid - left
nupper = right - mid
temp = [0] * (nlower + nupper)
ilower, iupper, k = left, mid, 0
while ilower < mid and iupper < right:
if x[ilower] <= x[iupper]:
temp[k] = x[ilower]
ilower += 1
k += 1
else:
temp[k] = x[iupper]
iupper += 1
k += 1
if ilower == mid:
temp[k:] = x[iupper:right]
else:
temp[k:] = x[ilower:mid]
x[left:right] = temp
return x
您將調用為：
x = random.sample(range(0, 30), 15)
ms(x, 0, len(x))
添加回答
舉報
0/150
提交
取消