# python归并排序求逆序数问题

``````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']

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()

1 个回答