我在我的算法书(Intro to algorithms 3rd edition Cormen)中读到有关合并排序(就地)的内容，我决定用 Python 实现它。问题是我找不到我做错了什么……我在 C++ 中看到了一些代码，但即使这样我也无法修复它。
这是我的代码:
def MERGE(A,start,mid,end):
L=[0]*(mid - start + 1)
for i in range(len(L) - 1):
L[i] = A[start+i]
L[len(L) - 1] = 100000 # centinel, (fix)
R=[0]*(end - mid + 2)
for j in range(len(R) - 1):
R[j] = A[mid+j]
R[len(R) - 1] = 100000
i = 0
j = 0
k = start
for l in range(k,end):
if(L[i] < R[j]):
A[l] = L[i]
i = i + 1
else:
A[k] = R[j]
j = j + 1
def mergeSort(A,p,r):
if p < r:
mid = int((p+r)/2)
mergeSort(A,p,mid)
mergeSort(A,mid+1,r)
MERGE(A,p,mid,r)
A = [20, 30, 15, 21, 42, 45, 31, 0, 9]
mergeSort(A,0,len(A)]
当我运行代码时，我遇到了一些索引问题:
File "myrealmerge.py", line 9, in MERGE
R[j] = A[mid+j]
IndexError: list index out of range
我知道这是一个“愚蠢的问题”并且有一些相关的帖子，但我尝试了那里的建议但它对我不起作用......
谁能帮帮我？吨 谢谢!
请您参考如下方法:
这段代码工作正常:
def MERGE(A,start,mid,end):
L = A[start:mid]
R = A[mid:end]
i = 0
j = 0
k = start
for l in range(k,end):
if j >= len(R) or (i < len(L) and L[i] < R[j]):
A[l] = L[i]
i = i + 1
else:
A[l] = R[j]
j = j + 1
def mergeSort(A,p,r):
if r - p > 1:
mid = int((p+r)/2)
mergeSort(A,p,mid)
mergeSort(A,mid,r)
MERGE(A,p,mid,r)
A = [20, 30, 21, 15, 42, 45, 31, 0, 9]
mergeSort(A,0,len(A))
print A
我尽量减少对您代码的更改。
祝你好运!
(已添加)
您可以使用此代码检查划分过程。
def MERGE(A,start,mid,end):
# Do nothing
pass
def mergeSort(A,p,r):
if r - p > 1:
mid = int((p+r)/2)
print A[p:mid],A[mid:r]
mergeSort(A,p,mid)
mergeSort(A,mid,r)
MERGE(A,p,mid,r)
A = [20, 30, 21, 15, 42, 45, 31, 0, 9]
mergeSort(A,0,len(A))
结果如下:
[20, 30, 21, 15] [42, 45, 31, 0, 9]
[20, 30] [21, 15]
[20] [30]
[21] [15]
[42, 45] [31, 0, 9]
[42] [45]
[31] [0, 9]
[0] [9]
这就是我们想要的。但是，'mid+1' 会产生无效结果。这是测试代码:
def MERGE(A,start,mid,end):
# Do nothing
pass
def mergeSort(A,p,r):
if r - p > 1:
mid = int((p+r)/2)
print A[p:mid],A[mid+1:r] # Changed
mergeSort(A,p,mid)
mergeSort(A,mid+1,r) # Changed
MERGE(A,p,mid,r)
A = [20, 30, 21, 15, 42, 45, 31, 0, 9]
mergeSort(A,0,len(A))
结果:
[20, 30, 21, 15] [45, 31, 0, 9]
[20, 30] [15]
[20] []
[45, 31] [9]
[45] []
(已添加)
这是使用“mid+1”的代码:
# New indexing function that includes the right index.
def get_partial_list(origin_list, left_index, right_index): # Added
return origin_list[left_index:right_index+1]
def MERGE(A,start,mid,end):
L = get_partial_list(A,start,mid)
R = get_partial_list(A,mid+1,end)
i = 0
j = 0
k = start
for l in range(k,end+1): # changed
if j >= len(R) or (i < len(L) and L[i] < R[j]):
A[l] = L[i]
i = i + 1
else:
A[l] = R[j]
j = j + 1
def mergeSort(A,p,r):
if r - p > 0: # changed
mid = int((p+r)/2)
mergeSort(A,p,mid)
mergeSort(A,mid+1,r) # changed
MERGE(A,p,mid,r)
A = [20, 30, 21, 15, 42, 45, 31, 0, 9]
mergeSort(A,0,len(A)-1) # changed
print A
我添加了新的索引功能。这是您期望的代码吗？
