python - python中的合并排序
问题描述
def get_random_array(n):
return [random.randint(0, 10000) for _ in range(n)]
def test_sorting_algorithm(algorithm):
for _ in range(100):
A = get_random_array(random.randint(0, 1000))
A_sorted = algorithm(A)
assert A_sorted == sorted(A), "FAIL!"
def merge(A,l,m,r):
i = l
j = m+1
new = []
while i <= m and j <= r:
if A[i] <= A[j]:
new.append(A[i])
i += 1
else:
new.append(A[j])
j += 1
while i <= m:
new.append(A[i])
i += 1
while j <= r:
new.append(A[j])
j += 1
return new
def mergeSort_rec(A, l, r):
if l < r:
m = (l+(r-1))//2 # Same as (l+r)//2, but avoids overflow for large l and h
# Sort first and second halves
mergeSort_rec(A, l, m)
mergeSort_rec(A, m+1, r)
merge(A, l, m, r)
def mergeSort(B):
A = B[:] # Copy the array just because we decided to return a sorted copy of the original array
mergeSort_rec(A, 0, len(A)-1)
return A
A = get_random_array(10)
test_sorting_algorithm(mergeSort)
test_sorting_algorithm
返回失败。此代码不起作用,因为merge
函数中的错误,您能帮我了解错误是什么以及如何修复它吗?此外,我不明白这条评论“# 与 (l+r)//2 相同,但避免大 l 和 h 溢出”的意思,你能解释一下这是什么意思吗?
解决方案
这种说法没有意义:
return new
由于您无处使用该函数的返回。所以这个函数merge()
什么都不做。
我相信您需要A
直接在函数内部更改数组。无需创建和返回new
数组。
推荐阅读
- django - django shell_plus:自动重载不起作用
- c# - Unity 设置 GUI 元素相对于不同画布上的另一个元素的位置
- c++ - c ++函数声明,头文件中的构造函数
- mongodb - 在嵌套数组中推送消息(Mongodb)
- html - 如何用html制作操作系统?
- angular - Angular中的对象属性值清理问题
- python - 如何在 Python 中使用 OpenCV 制作运动计数器?
- digital-ocean - 如何在数字海洋应用平台更新github源码?
- formal-verification - 无法证明仅依赖于实现/内联的基本功能
- acumatica - 可以将记录计数添加到分页网格吗?