python - TypeError：列表索引必须是整数，而不是在堆排序中浮动

Question

我在这里找不到我的错误，如果有人可以帮助我，那就太好了。

def heapsort (lista) :
    n= len(lista)-1
    k= n/2 
    while (k>0) :
        downheap(lista,n,k) 
        k-=1 
    while (n>=0) :
        (lista[1]),(lista[n])=(lista[n]),(lista[1]) 
        n-=1 
        return downheap(lista, n, 1) 
    return lista  

def downheap (lista, n, k) :
    v= lista[k] 
    while (k<=(n/2)) :
        j=k+k
        if (j<n and (lista[j]) == (lista[j])) :
            break
        (lista[k]) = (lista[j]) 
        k = j 
    lista[k] = v 

错误：

>>> heapsort([4,2,3,1])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 5, in heapsort
  File "<stdin>", line 2, in downheap
TypeError: list indices must be integers, not float

Answer 1

在 Python 3 中，使用/除法运算符总是返回一个float值：

>>> 2/2
1.0
>>> 3/2
1.5

改为使用楼层除法，//操作员：

k = n // 2

//运算符总是返回一个整数，将结果取底：

>>> 2//2
1
>>> 3//2
1

也许您是从 Python 2 中的示例编写函数的；在 Python 2 中，/操作符是一个模棱两可的操作符；当两个操作数都是整数时，它的作用就像地板除法运算符，但是如果任何一个操作数都是浮点数，那么它的行为就会突然不同，而是返回浮点除法结果。因为代码中的两个操作数都是整数，所以在 Python 2 中，您的代码不会抛出该异常。

你的下一个问题是它downheap()不返回任何东西，所以当你使用return downheap(lista, n, 1)inheapsort()你会返回None。我怀疑return有错误。

Answer 2

除法时只需转换为 int

def heapsort (lista) :
    n= len(lista)-1
    k= int(n/2)                       // instead of k= n/2 
    while (k>0) :
        downheap(lista,n,k) 
        k-=1 
    while (n>=0) :
        (lista[1]),(lista[n])=(lista[n]),(lista[1]) 
        n-=1 
        return downheap(lista, n, 1) 
    return lista