python - Merge_Sort 算法的计数工作

Question

所有，我想计算使用合并排序算法对数组进行排序的接近程度。我可以使用 Merge Sort 来排列数组，但我无法继续计算在此过程中需要多少次倒置。

比如输入[9,4,8​​,3]时，我想得到输出[3,4,8,9]和4次反转。反转的定义是:如果 b 在 B 中，c 在 C 中并且我们有 b>c 则需要反转(B，C 的顺序很重要)。首先，我将得到两个部分 ([4,9],1) 和 ([3,8],1)，它们分别表示一个反转。然后，当它们再次合并时，又出现了两次反转:选择 3 而不是 4，选择 8 而不是 9。

我的主要问题可能与算法本身无关。它是关于如何让我的变量之一在函数的函数循环中进化。 (我在 Merge_Sort 函数中使用了 Merge_Sort 函数)

def Merge_Sort(a):
    n = len(a)
    if n==1:
        if not 'total_rev' in vars():            
            total_rev = 0
        else:
            total_rev += rev_ind
    return a , total_rev
    else:
        m = math.floor(n/2)
        b , rev_ind_b = Merge_Sort(a[:m])
        if not 'total_rev' in vars():
            total_rev = 0
        else:
            total_rev += rev_ind_b
        c , rev_ind_c = Merge_Sort(a[m:])
        if not 'total_rev' in vars():
            total_rev = 0
        else:
            total_rev += rev_ind_c      
        a_sort , rev_ind = Merge(b,c)
        if not 'total_rev' in vars():
            total_rev = 0
            total_rev += rev_ind
        else :
            total_rev += rev_ind
        return a_sort , total_rev

def Merge(b,c):
    p = len(b)
    q = len(c)
    d = []
    reverse_ind = 0
    while len(b)!=0 or len(c)!=0 :
        if (len(b)*len(c) != 0) :
            b0 = b[0]
            c0 = c[0]
            if b0 <= c0 :
                d.append(b0)
                b.remove(b[0])
            else :
                reverse_ind += 1
                d.append(c0)
                c.remove(c[0])
        else :
            d.extend(b)
            b=[]
            d.extend(c)
            c=[]
    return d,reverse_ind

Merge 功能可以很好地工作。唯一的问题是我不能按照我的意愿更新变量“total_inv”。每当未定义时，我都会尝试定义“total_inv”。不确定这是否是一个好方法，因为它使我的代码变得困惑。我也尝试使用全局变量，但效果不佳。谢谢!

Answer 1

比这更简单:

• 在最深的递归级别 (n==1) 时，只需返回 0 作为交换次数。其逻辑是，您应该在该递归级别按原样返回列表的交换次数，而无需考虑更大的列表可能是什么。因此，当 n==1 您的列表只有一个值时，显然不需要交换。
• 在其他情况下，只需将您从递归调用中获得的计数相加即可。这样，当冒泡返回递归树时，它们会增加。

这是为 Merge_Sort 改编的代码:

def Merge_Sort(a):
    n = len(a)
    if n==1:
        return a, 0 # at deepest recursion always return 0 for the number of swaps
    else:
        m = n//2 # use integer division; you don't need `math.floor`
        b , rev_ind_b = Merge_Sort(a[:m])
        c , rev_ind_c = Merge_Sort(a[m:])
        a_sort , rev_ind = Merge(b,c)
        return a_sort , rev_ind_b + rev_ind_c + rev_ind # add the numbers