2

计算归并排序中反转次数的代码:

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

为什么数字的十位和个位是分开的?

4

4 回答 4

4

你做错了两件事:

  • 您没有将文本转换为整数
  • 您正在使用.extend()添加到列表中。

这两个错误共同导致您的代码失败。

利用:

for line in inFile:
    a.append(int(line))

反而。

Python 字符串也是序列。使用a.extend()将输入序列的每个元素添加到列表中;对于表示单个字符的字符串:

>>> a = []
>>> a.extend('foo')
>>> a
['f', 'o', 'o']

list.append()另一方面,将单个值添加到列表中:

>>> a = []
>>> a.append('foo')
>>> a
['foo']

int()对空格不太挑剔,因此即使您的line值包含换行符,int(line)也可以使用:

>>> int('46\n')
46
于 2013-07-15T12:46:01.443 回答
1

append 将一个元素添加到列表中,extend 将第一个列表与另一个列表连接起来使用 a.append(fields) 并且它会正常工作。

于 2013-07-15T12:55:24.657 回答
1

您使用list.extendextend接受一个可迭代对象并对其进行迭代,它逐个字母地迭代字符串。

>>> a = []
>>> a.extend('123')
>>> a
['1', '2', '3']
>>> 

我想你想要的是list.append

于 2013-07-15T12:46:08.023 回答
0
with open('a1.txt') as f:
  a = list(int(i) for i in f if i.strip())

print(a)

最后一个if i.strip()是跳过空行。

于 2013-07-15T12:51:28.277 回答