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

合并功能可以正常使用。唯一的问题是我不能按我的意愿保持变量 "total_inv" 更新。每当未定义时，我都会尝试定义 "total_inv" 。不确定这是否是一个好方法，因为它使我的代码变得混乱。我也尝试使用全局变量，但效果不佳。谢谢！

Answer 1

比这更简单：

在最深的递归级别 (n==1) 时，交换次数仅为 return 0。逻辑是你应该 return 列表的交换次数 在那个递归级别 ，而不考虑更大的列表可能是什么。所以当 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

Merge_Sort 算法的计数工作

Count work for Merge_Sort Algorithm

python

algorithm

mergesort

global-variables

count