算法学习笔记(3):插入排序、归并排序与逆序数

前些天在挨个做hackerrank上的题目的时候,碰到了这么一道题

题目的完成率并不高,只有百分之三十六点多,我估计了下难度,自己应该是做不出来的,最后果然没做出来。不过在Discussion下面还是看到了些有用的帮助,有人说用mergesort能做出来。于是又仔细的想了想,还是花了些力气做出来了...

题目的内容是计算插入排序一个序列的移动元素的总次数。实际上是计算的序列的逆序数

逆序数的定义上面那个wiki的链接里说的挺清楚的了,数的就是反序排列的数字对数。

比如[1,3,2]的逆序数是1,在插入排序的时候,2会向左移动一次,整个序列变成了[1,2,3]。

[2,3,1]的逆序数是2,在插入排序的时候,1会向左移动两次,整个序列变成[1,2,3]。

hackerrank在排序这一章前面也有一道题是计算插入排序移动次数的,当时按照题目的提示,使用的直接在插入排序的时候,移动一次,加一次,最后依次数出来移动的次数。当然这个的时间复杂度就是,在序列比较长的情况下很容易超时。这种比较『暴力』的方法,显然不适合本题。

mergesort是一种比较简单的方法。可以很容易的想象出,在merge过程中,如果『小序列』非空,每当『大序列』的最小元素被选出来,就意味着逆序数需要自增目前『小序列』中元素个数那么多,因为这个时候『小序列』中的所有元素都比位于他们之后的『大序列』中挑出的最小元素大。

而且mergesort的时间复杂度是,已经是比较排序的最优了,所以也理应在本题中不会超时。

知道这个关键点,代码实现就很容易了,就是增添个自增的语句而已,代码如下所示。

def merge(a,b):
    global answer
    a_flag = 0
    b_flag = 0
    result = []
    while a_flag<len(a) and b_flag<len(b):
        if a[a_flag]>b[b_flag]:
            result.append(b[b_flag])
            answer+=(len(a)-a_flag)
            b_flag+=1
        else:
            result.append(a[a_flag])
            a_flag+=1
    if a_flag==len(a):
        result.extend(b[b_flag:])
    else:
        result.extend(a[a_flag:])
    return result

def mergesort(l):
    if len(l)>1:
        mid = len(l)/2
        a = l[:mid]
        b = l[mid:]
        a = mergesort(a)
        b = mergesort(b)
        return merge(a,b)
    else:
        return l

n = input()
for iterate in range( n ):
    x = input()
    a = [ int( i ) for i in raw_input().strip().split() ]
    answer = 0
    mergesort(a)
    print answer