python - Python通过合并排序计算倒数得到错误

Question

我正在尝试使用 Python 计算长文本文件中的反转次数。我不断收到错误消息left = sortCount(alist, len1, i)

import csv


def mergeCount(alist, i, len1, len2):
    print("Merge")
    inv = 0
    temp = []
    index1 = i
    index2 = i + len1

    while index1 < i + len1 and index2 < i + len1 + len2:
        if alist[index1] <= alist[index2]:
            temp.append(alist[index1])
            index1 += 1
        else:
            temp.append(alist[index2])
            index2 += 1
            inv += i + len1 - index1

    if index2 == i + len1 + len2:
        temp.extend(alist[index1 : i + len1])
    else:
        pass

    write = i
    for value in temp:
        alist[write] = value
        write += 1

    return inv


def sortCount(alist, n, i=0):
    #print("Sort")
    if len(alist) <= 1:
        return 0
    else:
        len1 = n // 2
        len2 = n // 2 + n % 2
        left = sortCount(alist, len1, i)
        right = sortCount(alist, len2, i + len1)
        mergeInv = mergeCount(alist, i, len1, len2)

        return left + right + mergeInv

def safeint(val):
   try:
      return int(val)
   except ValueError:
      return val

alist = []

with open('IntegerArray.txt') as f:
    lines = csv.reader(f, delimiter='\n')
    for line in lines:
        line = map(safeint, line)
        alist.append(line)

print sortCount(alist, len(alist), 0)

Answer 1

当len1成为 时zero，你不断地left = sortCount(alist, 0, i)一次又一次地调用同样的东西。

如果len1==0返回0

if len1==0:
        return 0

left = sortCount(alist, len1, i)
right = sortCount(alist, len2, i + len1)

修改你sortCount喜欢的样子：

    def sortCount(alist, n, i=0):
    if len(alist) <= 1:
        return 0
    else:
        len1 = n // 2
        len2 = n // 2 + n % 2

        if len1==0:
            return 0

        left = sortCount(alist, len1, i)
        right = sortCount(alist, len2, i + len1)
        mergeInv = mergeCount(alist, i, len1, len2)
    return left + right + mergeInv