python中的合并排序

abpan8
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返回FAIL。此代码不起作用,因为merge函数中有错误,您能帮我了解错误是什么以及如何修复它吗?此外,我不明白这条评论“#Same as (l+r)//2,但避免大 l 和 h 溢出”的意义,你能解释一下这是什么意思吗?

尤里·克里希奇

这种说法没有意义:

return new

由于您无处使用该函数的返回。所以这个函数merge()什么都不做。

我相信您需要A直接在函数内部更改数组无需创建和返回new数组。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

TOP 榜单

热门标签

归档