合并排序算法 - 计算反转

Question

可以理解的是,为合并排序算法和计数反转创建了多个线程.虽然这是课程课程的家庭作业问题,但我很难理解在计算反演次数时我的实施方法出错了.与参加该课程的其他人相比,对于少数测试示例,我似乎得到了非常不切实际的低值.以下是我的代码:

count = 0
def sort_list(unsortedlist):

    m = len(unsortedlist)

    A_list = unsortedlist[:m/2]
    B_list = unsortedlist[m/2:]


    if len(A_list) > 1: # if the list is longer thn 2 items, break it up
        A_list = sort_list(A_list)


    if len(B_list) > 1: # breaking and sorting second part
        B_list = sort_list(B_list)

    return merge_sort(A_list,B_list) # merge the smaller lists to return either a-list/b_list or full_list        

def merge_sort(a_list,b_list):

    initiallist = a_list+b_list
    final_list = []
    i = 0
    j = 0
    global count

    while len(final_list) < (len(initiallist)):

        if len(a_list) != 0 and len(b_list) != 0:
            if  a_list[i] < b_list[j]:
                final_list.append(a_list.pop(i))

            elif a_list[i] > b_list[j]:
                final_list.append(b_list.pop(j))
                count += 1

            elif a_list[i] == b_list[j]:
                final_list.append(a_list[i])
                final_list.append(b_list[j])


        elif len(b_list) == 0 :
            final_list+=a_list


        elif len(a_list) == 0 :
            final_list+=b_list

    print count

    return final_list

Answer 1

问题是,如果a_list[i] > b_list[j]是真的,你只计算1次反转.

但是由于这两个列表都是在这一点上排序的,这意味着你得到了每个元素的反转a_list.所以你必须使用count += len(a_list)而不是count += 1.

示例:

a_list = [5,6,7,8] 和 b_list = [1,2,3,4]

1. 5 > 1
   • final_list = [1]
   • 你得到四次倒置:(5,1),(6,1),(7,1),(8,1)
2. 5 > 2
   • final_list = [1,2]
   • 得到四次倒置:(5,2),(6,2),(7,2),(8,2)
3. 5 > 3
   • final_list = [1,2,3]
   • 你得到四次倒置:(5,3),(6,3),(7,3),(8,3)
4. 5 > 4
   • final_list = [1,2,3,4]
   • 你得到四次倒置:(5,4),(6,4),(7,4),(8,4)
5. b_list 是空的
   • 追加a_list到final_list并获得final_list = [1,2,3,4,5,6,7,8]
   • 没有更多的反转