具有合并功能的计数版本算法

Question

我正在尝试编写计数版本算法的最佳版本。我在第 84 行遇到此错误：int 对象不可迭代。

但我不明白为什么我会遇到这个问题。

函数mergesort：按递增顺序合并一个数字列表（这个在我单独使用时有效）

函数merge_and_count: 取两个合并后的数组作为输入，统计左边数组中大于右边数组元素的个数

函数sort_and_count：给出反转次数的函数（它也是return一个列表，因为它允许我使用递归）

代码如下：

def mergesort(list):
    """Fonction qui classe les nombres de la liste par ordre croissant.
        Celle la fonctionne bien et renvoie une liste"""
    taille = len(list)
    liste_1_temp = []
    liste_2_temp = []


    if len(list) > 1:

        for i in range(0,(taille//2)):
            liste_1_temp.append(list[i])

        for i in range((taille//2),taille):
            liste_2_temp.append(list[i])
        mergesort(liste_1_temp)
        mergesort(liste_2_temp)

        i = 0
        j = 0
        k = 0
        while i < len(liste_1_temp) and j < len(liste_2_temp):
            if liste_1_temp[i] < liste_2_temp[j]:
                list[k] = liste_1_temp[i]
                i+=1
                k+=1
            else:
                list[k] = liste_2_temp[j]
                j += 1
                k+=1
        while (i < len(liste_1_temp)):
            list[k] = liste_1_temp[i]
            i+=1
            k+=1

        while (j < len(liste_2_temp)):
            list[k] = liste_2_temp[j]
            j+=1
            k+=1
    liste_finale = list
    return liste_finale



def merge_and_count(A,B):
    """Fonction qui doit renvoyer """

    i = 0
    j = 0
    count = 0
    C = []

    while (i < len(A)):
        if A[i] > B[j]:
            C.append(B[j])
            count += (len(A)-i)
            i = 0
            j += 1
        else:
            C.append(A[i])
            i += 1
    return count,C



def sort_and_count(L):

    i = 0
    A = []
    B = []

    if len(L) == 1:
        return 0

    else:
        size = len(L)
        size2 = len(L) // 2

        for i in range(0, size2):
            A.append(L[i])
        for i in range(size2,size-1):
            B.append(L[i])

        (rA,A) = sort_and_count(A)
        (rB,B) = sort_and_count(B)
        (r,L) = merge_and_count(mergesort(A),mergesort(B))

        return ((rA+rB+r),L)

Answer 1

您忘记 return 来自 sort_and_count 的一对：

def sort_and_count(L):

    i = 0
    A = []
    B = []

    if len(L) == 1:
        return 0  # <-- You forgot to return the list as second element
    ...
    ...

因为这些行

    (rA,A) = sort_and_count(A)
    (rB,B) = sort_and_count(B)

期望在赋值运算符的右侧有一个可迭代对象并且只得到一个整数，你会得到 int object is not iterable 错误。

具有合并功能的计数版本算法

Counting Version algorithm with merge function

python

algorithm

inversion