递归归并排序统计merge_sort调用与merge比较次数如何不使用全局变量

修改方案 #

我们可以调整函数的返回值结构，让递归过程中逐层传递并累加统计值，完全不需要依赖全局变量：

• merge 函数额外返回单次合并的比较次数
• merge_sort 函数额外返回当前递归分支的总调用次数、总比较次数，每次递归时累加子分支的统计值即可

修改后代码 #

import numpy as np

def merge_sort(array):
    # 本次调用计数+1
    current_call = 1
    current_compare = 0
    n = len(array)
    if n <= 1:
        return array, current_call, current_compare

    # 递归处理左右子数组，接收子分支的统计值
    arr1, call1, cmp1 = merge_sort(array[0:n // 2])
    arr2, call2, cmp2 = merge_sort(array[n // 2:n])
    
    # 合并并接收本次合并的比较次数
    new_arr, merge_cmp = merge(arr1, arr2)

    # 累加所有统计值
    total_call = current_call + call1 + call2
    total_compare = cmp1 + cmp2 + merge_cmp
    return new_arr, total_call, total_compare


def merge(arr1, arr2):
    new_arr = np.empty(len(arr1) + len(arr2), dtype=int)
    ind = 0
    i = 0
    j = 0
    com_num = 0   # 统计本次合并的比较次数
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            com_num += 1
            new_arr[ind] = arr1[i]
            i += 1
            ind += 1
        else:
            com_num += 1
            new_arr[ind] = arr2[j]
            j += 1
            ind += 1

    while i < len(arr1):
        new_arr[ind] = arr1[i]
        i += 1
        ind += 1

    while j < len(arr2):
        new_arr[ind] = arr2[j]
        j += 1
        ind += 1

    return new_arr, com_num

使用示例 #

if __name__ == "__main__":
    test_arr = [3, 1, 4, 1, 5, 9, 2, 6]
    sorted_arr, total_call, total_compare = merge_sort(test_arr)
    print("排序结果：", sorted_arr)
    print("merge_sort总调用次数：", total_call)
    print("merge总比较次数：", total_compare)

可选方案 #

如果你不想修改原有函数的返回值结构，也可以把计数存入可变容器（比如列表）作为参数传递，利用可变对象的特性实现跨调用修改：

def merge_sort(array, cnt):
    cnt[0] += 1 # cnt[0]存调用次数，cnt[1]存比较次数
    n = len(array)
    if n <=1:
        return array
    arr1 = merge_sort(array[:n//2], cnt)
    arr2 = merge_sort(array[n//2:], cnt)
    return merge(arr1, arr2, cnt)

def merge(arr1, arr2, cnt):
    new_arr = np.empty(len(arr1) + len(arr2), dtype=int)
    ind = 0
    i = 0
    j = 0
    com_num = 0
    # 合并逻辑和原有代码完全一致
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            com_num += 1
            new_arr[ind] = arr1[i]
            i += 1
            ind += 1
        else:
            com_num += 1
            new_arr[ind] = arr2[j]
            j += 1
            ind += 1
    while i < len(arr1):
        new_arr[ind] = arr1[i]
        i += 1
        ind += 1
    while j < len(arr2):
        new_arr[ind] = arr2[j]
        j += 1
        ind += 1
    cnt[1] += com_num
    return new_arr

# 调用方式
cnt = [0, 0]
sorted_arr = merge_sort(test_arr, cnt)
print("调用次数：", cnt[0], "比较次数：", cnt[1])

内容的提问来源于stack exchange，提问作者Captain Toad