我正尝试在 python 中实现合并排序,如下所示:
def MergeSortTopdown(list_n):
#Base condition to stop recursion
if len(list_n) == 1:
return list_n
else:
mid = int(len(list_n)/2)
first_half = list_n[:mid]
second_half = list_n[mid:]
MergeSortTopdown(first_half)
MergeSortTopdown(second_half)
i = 0
j = 0
n = len(list_n)
for k in range(n):
if j >= len(first_half) and i < len(second_half):
list_n[k] = first_half[i]
i += 1
if i >= len(first_half) and j < len(second_half):
list_n[k] = second_half[j]
j += 1
if i < len(first_half) and j < len(second_half):
if first_half[i] > second_half[j]:
list_n[k] = second_half[j]
j += 1
elif second_half[j] > first_half[i]:
list_n[k] = first_half[i]
i += 1
elif second_half[i] == first_half[j]:
list_n[k] = first_half[i]
if i>j:
i += 1
else:
j += 1
return list_n
当我用已经排序的列表进行测试时,这似乎是合理的。但是,当我运行时,出现此错误:
MergeSortTopdown([3,4,6,7,1,8,56,112,67])
Traceback (most recent call last):
File "<ipython-input-11-29db640f4fc6>", line 1, in <module>
MergeSortTopdown([3,4,6,7,1,8,56,112,67])
File "C:/Users/Emmanuel Hoang/MergeSortTopDown.py", line 13, in MergeSortTopdown
MergeSortTopdown(second_half)
File "C:/Users/Emmanuel Hoang/MergeSortTopDown.py", line 13, in MergeSortTopdown
MergeSortTopdown(second_half)
File "C:/Users/Emmanuel Hoang/MergeSortTopDown.py", line 19, in MergeSortTopdown
list_n[k] = first_half[i]
IndexError: list index out of range
你能告诉我我的代码有什么问题吗,有什么方法可以改进我的代码。提前谢谢你
最佳答案
您已尝试引用列表末尾之后的元素。我在您的代码中添加了一些简单的 print
语句:
for k in range(n):
print("LOOP TOP", k, first_half, second_half, list_n)
if j >= len(first_half) and i < len(second_half):
print("TRACE", list_n, k, "\t", first_half, i)
list_n[k] = first_half[i]
i += 1
然后我将输入列表缩短为 [8,56,112,3,67]
。
输出:
LOOP TOP 0 [8] [56] [8, 56]
LOOP TOP 1 [8] [56] [8, 56]
LOOP TOP 0 [3] [67] [3, 67]
LOOP TOP 1 [3] [67] [3, 67]
LOOP TOP 0 [112] [3, 67] [112, 3, 67]
LOOP TOP 1 [112] [3, 67] [3, 3, 67]
TRACE [3, 3, 67] 1 [112] 0
LOOP TOP 2 [112] [3, 67] [3, 67, 67]
TRACE [3, 67, 67] 2 [112] 1
接下来是您遇到的崩溃。当只有元素 0 时,您尝试获取 first_half[1]
。
分析
您有三个连续的 if
语句来检查列表边界:
if j >= len(first_half) and i < len(second_half):
if i >= len(first_half) and j < len(second_half):
if i < len(first_half) and j < len(second_half):
您在第一次检查中切换了 i
和 j
:i
是 first_half
下标。此更改修复了合并:
if i < len(first_half) and j >= len(second_half):
建议
您的部分问题是您的合并逻辑过于复杂。在循环的主要部分,您有一个单一的值检查:将较低的列表头移动到合并列表。在两个指数都在范围内时执行此操作。
然后,当一个索引到达其列表的末尾时,退出循环并添加另一个列表的剩余元素。使用 extend
方法。所以……
while i < len(first_half) and j < len(second_half):
if first_half[i] < second_half[j]:
# move smaller element to list_n;
# increment i or j as needed
k += 1
# One of these will be an empty operation.
list_n.extend(first_half[i:])
list_n.extend(second_half[j:])
关于python - 在python中实现合并排序时出现错误,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53218526/