Python mergesort：沒有多個函數調用的倒數計數

我想計算在Python中使用一個簡單函數定義（即一個def語句用於mergesort）的mergesort算法的以下實現中發生的反轉次數，。我評論過這個歸併算法清晰：Python mergesort：沒有多個函數調用的倒數計數

import csv 

def safeint(val): 
    try: 
     return int(val) 
    except ValueError: 
     return val 

list = [] 
with open('file.txt') as f: 
    lines = csv.reader(f, delimiter='\n') 
    for line in lines: 
     line = map(safeint, line) 
     list.append(line) 

def mergesort(list): 
    mid = len(list)//2 #MIDPOINT FOR DIVISION 
    lft, rgt = list[:mid], list[mid:] 
    if len(lft) > 1: lft = mergesort(lft) #SORT BY HALVES 
    if len(rgt) > 1: rgt = mergesort(rgt) 
    res = [] 
    while lft and rgt: #NEITHER HALF IS EMPTY 
     if lft[-1] >=rgt[-1]: #lft HAS GREATEST LAST VALUE 
      res.append(lft.pop()) #APPEND IT 
     else: #rgt HAS GREATEST LAST VALUE 
      res.append(rgt.pop()) #APPEND IT 
    res.reverse() #RESULT IS BACKWARD 
    return (lft or rgt) + res #ALSO ADD THE REMAINDER 

print mergesort(list)

我的輸入，file.txt的，是下面的形式：

我的輸出（如預期）：

[[1], [2], [3], [4], [5], [19], [55], [60], [82]]

是否可以在不添加額外的def語句的情況下將「反演計算器」合併到此代碼中？網上已有很多多功能示例，例如：Counting Inversions Using Merge Sort，https://codereview.stackexchange.com/questions/12922/inversion-count-using-merge-sort

我們能比這更簡潔嗎？

來源

2015-07-06 warship

的Python上下的僞代碼：

while lft and rgt: #NEITHER HALF IS EMPTY 
    if lft[-1] >=rgt[-1]: #lft HAS GREATEST LAST VALUE 
     # if the last of lft is greater than the last of rgt (which is sorted), 
     # then it is also greater than everything before the last element of rgt, 
     # so it generates as many inversions as the remaining elements in rgt 
     inversions += len(rgt) 
     res.append(lft.pop()) #APPEND IT 
    else: #rgt HAS GREATEST LAST VALUE 
     res.append(rgt.pop()) #APPEND IT

哪裏inversions要麼是一個全球性的一個參數（例如使其成爲1個元素列表，所以它是可變的）或東西，你返回（確保返回的總和在這種情況下，兩半的倒數）。

來源

2015-07-06 07:38:24 IVlad

Python mergesort：沒有多個函數調用的倒數計數

回答

相關問題