合并排序算法-计数反转

Durga 发表于 Dev

杜尔加

可以理解，为合并排序算法和计数反转创建了多个线程。虽然这是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

AbcAeffchen

问题是，如果计数为1，则仅计算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]

5 > 1
- final_list = [1]
- 您将得到四个反转：（5,1），（6,1），（7,1），（8,1）
5 > 2
- final_list = [1,2]
- 您将获得四个反演：（5,2），（6,2），（7,2），（8,2）
5 > 3
- final_list = [1,2,3]
- 您得到四个反转：（5,3），（6,3），（7,3），（8,3）
5 > 4
- final_list = [1,2,3,4]
- 您将得到四个反转：（5,4），（6,4），（7,4），（8,4）
b_list 是空的
- 追加a_list到final_list和GETfinal_list = [1,2,3,4,5,6,7,8]
- 不再反转