count_inversions in an integer list
博客专区 > ludlows 的博客 > 博客详情
count_inversions in an integer list
ludlows 发表于3年前
count_inversions in an integer list
  • 发表于 3年前
  • 阅读 0
  • 收藏 0
  • 点赞 0
  • 评论 0

标题:腾讯云 新注册用户域名抢购1元起>>>   

count = 0

def merge_sort(li):

    if len(li) < 2: return li 
    m = len(li) / 2 
    return merge(merge_sort(li[:m]), merge_sort(li[m:])) 

def merge(l, r):
    global count
    result = [] 
    i = j = 0 
    while i < len(l) and j < len(r): 
        if l[i] < r[j]: 
            result.append(l[i])
            i += 1 
        else: 
            result.append(r[j])
            count = count + (len(l) - i)
            j += 1
    result.extend(l[i:]) 
    result.extend(r[j:]) 
    return result
filename = 'Integer.txt'
unsorted = []
inFile = open(filename, 'r')
lines = inFile.readlines()
for i in lines:
    content = i.strip('\n')
    unsorted.append(int(content))



merge_sort(unsorted)
print count


共有 人打赏支持
粉丝 0
博文 15
码字总数 4195
×
ludlows
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: