佚名通过本文主要向大家介绍了python归并排序,归并排序求逆序对,归并排序 逆序数,归并求逆序数,归并求逆序对等相关知识,希望对您有所帮助,也希望大家支持linkedu.com www.linkedu.com
问题：python归并排序求逆序数问题
描述:
解决方案1:
描述:
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()
解决方案1:
就是个边界条件的问题，不等号加上或者去掉等号