合併排序算法 - 倒計數

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

的問題是，你是隻算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]
   • 不再倒置