计算归并排序中反转次数的代码:
count =0
def merge(left,right):
"""Assumes left and right are sorted lists.
Returns a new sorted list containing the same elements
as (left + right) would contain."""
result = []
global count
i,j = 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i = i + 1
else:
result.append(right[j])
j = j + 1
count+=len(left[i:])
while (i < len(left)):
result.append(left[i])
i = i + 1
while (j < len(right)):
result.append(right[j])
j = j + 1
return result
def mergesort(L):
"""Returns a new sorted list with the same elements as L"""
if len(L) < 2:
return L[:]
else:
middle = len(L) / 2
left = mergesort(L[:middle])
right = mergesort(L[middle:])
together = merge(left,right)
return together
a=[]
inFile=open('a1.txt','r')
for line in inFile:
fields=line.strip()
a.extend(fields)
print mergesort(a)
print count
其中a1.txt
包含:
46
45
44
43
42
为文件中的整数显示的列表应为:
[42, 43, 44, 45, 46]
但输出是
['2', '3', '4', '4', '4', '4', '4', '4', '5', '6']
为什么数字的十位和个位是分开的?