python归并排序求逆序数问题

Question

class nx:  
    count = 0
    def __init__(self):    
        self.str_list=[]
        self.N = int(raw_input().strip())
        for _ in xrange(self.N):
            self.str_list.append(raw_input().strip())
        print self.count_inversion(self.str_list)

    def merge(self, ListA, ListB):
        self.newlist = []
        while ListA and ListB:
            if ListA[0] > ListB[0]:
               self.newlist.append(ListB[0])
               ListB = ListB[1:]
               self.count += len(ListA)
               print str(len(ListA))+'****   '
            else:
               self.newlist.append(ListA[0])
               ListA =ListA[1:]         
        if ListA:
            self.newlist = self.newlist + ListA  
        elif ListB:
            self.newlist = self.newlist + ListB        
        return self.newlist       

    def merge_sort(self, A):
        if len(A) == 1:
            return A
        else:
            self.middle = len(A)/2        
            print '**************'
            print 'Ais '+str(A)
            print 'middle is '+ str(self.middle)
            print 'zuo'
            print A[:self.middle]
            print 'you'
            print A[self.middle:]
            self.sa1 = self.merge_sort(A[:self.middle])
            self.sa2 = self.merge_sort(A[self.middle:])
            return self.merge(self.sa1, self.sa2)

    def count_inversion(self, sequence):
        self.merge_sort(sequence)
        return self.count
    if __name__ == '__main__':
        nx()

---

结果:

---

Ais ['2', '4', '3', '1']
middle is 2
zuo
['2', '4']
you
['3', '1']

---

Ais ['2', '4']
middle is 1
zuo
['2']
you
['4']

    ****************为什么会这样
    Ais ['4', '3', '1']
    middle is 1
    zuo
    ['4']
    you
    ['3', '1']
    ****************

Ais ['3', '1']
middle is 1
zuo
['3']
you
['1']

---

我知道了，python局部变量问题

class nx:
def init(self):
self.count = 0
self.str_list=[]
self.N = int(raw_input().strip())
for _ in xrange(self.N):
self.str_list.append(raw_input().strip())
print self.count_inversion(self.str_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_inversion(self, sequence):
    self.merge_sort(sequence)
    return self.count

if name == 'main':
nx()

---

Answer 1

就是个边界条件的问题，不等号加上或者去掉等号