合并排序算法 - 计数逆序对

Question

可以理解的是，关于归并排序算法和计算逆序对的问题，有很多人讨论和提问。这是一个在Coursera课程中的作业问题，但我在理解我的代码哪里出错，导致计算逆序对的数量时遇到了困难。我发现我的一些测试例子的结果非常不真实，数值比其他同学的要低得多。下面是我的代码：

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] 为真时，你只算了一次反转。

但因为这两个列表在这个时候都是排好序的，这意味着对于 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]
   • 没有更多的反转了