為什么我的歸并排序程序不工作？def merge(a, p, q, r): n1 = (q - p) + 1 n2 = r - q L = [0] * n1 M = [0] * n2 for i in range(n1): L[i] = a[i] for j in range(n2): M[j] = a[j] i = 0 j = 0 for k in range(p, r): if L[i] <= M[j]: a[k] = L[i] i += 1 else: a[k] = M[j] j += 1def merge_sort(a, p, r): if len(a) <= 1: print('list has only one element') else: q = len(a) // 2 merge_sort(a, p, q) merge_sort(a, q + 1, r) merge(a, p, q, r) a = [3,41,52,26,38,57,9,49]merge_sort(a, 0, len(a) - 1)for _ in range(len(a)): print('%d', a[_])
1 回答
12345678_0001
TA貢獻(xiàn)1802條經(jīng)驗(yàn) 獲得超5個(gè)贊
您的代碼中存在多個(gè)問(wèn)題：
切片的初始化循環(huán)不正確。索引a應(yīng)該分別從p和開(kāi)始q+1。將它們更改為：
for i in range(n1):
L[i] = a[p+i]
for j in range(n2):
M[j] = a[q+1+j]
或者簡(jiǎn)單地寫(xiě)：
L = a[p..q+1]
M = b[q+1..r+1]
這使得qandr應(yīng)該被排除在外而不是被包含在內(nèi)是顯而易見(jiàn)的。
合并循環(huán)不正確：范圍應(yīng)該是range(p, r+1)并且一旦一個(gè)臨時(shí)數(shù)組用完，比較指的是超出orL[i] <= M[j]邊界的元素。LM
q計(jì)算不正確merge_sort：它應(yīng)該是q = (p + r) // 2
測(cè)試if len(a) <= 1:不正確，您應(yīng)該測(cè)試切片是否至少有 2 個(gè)元素，如果沒(méi)有則什么也不做：
if p < r:
q = (p + r) // 2
merge_sort(a, p, q)
merge_sort(a, q + 1, r)
merge(a, p, q, r)
這是一個(gè)排除了上限的修改版本：
def merge(a, p, q, r):
L = a[p..q]
M = a[q..r]
i = 0
j = 0
for k in range(p, r):
if j >= len(M) or (i < len(L) and L[i] <= M[j]):
a[k] = L[i]
i += 1
else:
a[k] = M[j]
j += 1
def merge_sort(a, p, r):
if r - p > 1:
q = p + (r - p) // 2
merge_sort(a, p, q)
merge_sort(a, q, r)
merge(a, p, q, r)
a = [3,41,52,26,38,57,9,49]
merge_sort(a, 0, len(a))
for _ in range(len(a)):
print('%d', a[_])
添加回答
舉報(bào)
0/150
提交
取消