Devide and Conquer Counting Inversions with Python

本文主要内容关于python归并排序求逆序数的算法。

解决问题：给定有限长度的无重复乱序数组，求其逆序数个数。简单来说我们可以用两个循环来解决，但是复杂度为$O(N^2)$，若利用归并排序，复杂度就降为了$O(N \log(N))$。以下给出一个实现，

class Ivrs_num(object):

    def __init__(self, filename):
        self.count = 0
        self.filename = filename

    def load_txt(self):
        '''载入txt文件保存为list'''
        int_list = []
        with open(self.filename) as f:
            for line in f:
                int_list.append(int(line))
        return int_list

    def merge(self, ListA, ListB):
        '''将两个已经排序好的数组合并成新的排序好的数组
        顺便计算逆序数'''
        newList = []
        while ListA and ListB:
            if int(ListA[0]) > int(ListB[0]):
                self.count += len(ListA)
                newList.append(ListB.pop(0))
            else:
                newList.append(ListA.pop(0))
        return newList + ListA + ListB

    def merge_sort(self, A):
        '''归并排序'''
        if len(A) == 1: return A
        else:
            middle = len(A) // 2
            return self.merge(self.merge_sort(A[:middle]), self.merge_sort(A[middle:]))

    def count_ivrs(self):
        data = self.load_txt()
        self.merge_sort(data)
        return self.count

if __name__ == "__main__":
    ivrs = Ivrs_num("IntegerArray.txt")
    print ivrs.count_ivrs()