我ndexError:列表索引超出范围

Question

快速排序与复制程序钥匙。那个代码完美地运行一到两次，然后在下次事件中给出索引器错误，尽管列表不是空的。什么时候我打印出它们所在的索引范围。是我的电脑有问题吗？在

编辑添加了回溯

import random


def partition(n,lo,hi):
    i=lo
    lt=lo    #index showing the start of all duplicate partitioning keys
    gt=hi    #index showing the end of all duplicate partitioning keys
    x=n[lt]

    while(i<=gt):
        while(n[i]<=n[lt] and i<=gt):
            if(x!=n[lt]):
                print("alert!!!")
            if(n[i]<n[lt]): #current alement not a duplicate of partitioning alement
                if(lt<=i):
                    n[lt],n[i]=n[i],n[lt]
                    #print(n)
                i+=1
                lt+=1
            else: #current element is a duplicate partitioning alement
                #print(n[i],"=",n[lt])
                i+=1

        while(n[gt]>n[lt] and i<=gt):
            gt-=1

        if(i<gt):
            n[i],n[gt]=n[gt],n[i]
            gt-=1
            #print(n)


    return gt



def quickSort(n,lo,hi):
    #print("called")
    if(lo<hi):
        print(n)
        p=partition(n, lo, hi)
        quickSort(n, lo, p-1)
        quickSort(n, p+1, hi)

def main():
    nums=[]
    for i in range(30):
        nums.append(random.randrange(100))
    print("original array")
    print(nums)
    k=4
    hi=len(nums)-1
    #print(k,"th lowest number is ",quickSelect(nums, 0,hi,k))
    print(nums)
    quickSort(nums,0,hi)
    print(nums)

if __name__ == "__main__":
    main()  

回溯：

^{pr2}$

Answer 1

问题在第11排：

    while(n[i]<=n[lt] and i<=gt):

您需要将其更改为：

^{pr2}$

因为python首先检查第一个条件（在本例中是i<；=gt），如果它是真的，那么他会检查第二个条件（n[i]<；=n[lt]），但是如果第一个条件为false，那么python会退出while循环而不检查第二个条件。在

Answer 2

由于检查内部while循环中条件的顺序，代码有时会获得越界索引。在

通常，调试此类问题的最佳方法是向代码中添加try和except块，并使用except块打印出有用的诊断值。关于这个问题的循环I：

try:
    while(n[i]<=n[lt] and i<=gt):
        if(x!=n[lt]):
            print("alert!!!")
        if(n[i]<n[lt]): #current alement not a duplicate of partitioning alement
            if(lt<=i):
                n[lt],n[i]=n[i],n[lt]
                #print(n)
            i+=1
            lt+=1
        else: #current element is a duplicate partitioning alement
            #print(n[i],"=",n[lt])
            i+=1
except IndexError:
    print(i, gt, len(n))
    raise

您将看到在某些情况下，gt将是len(n) - 1，而{}将是{}。在这种情况下，while(n[i]<=n[lt] and i<=gt):中的第一个测试将引发一个IndexError，因为{}不是有效的索引。在

相反，您应该将测试放在另一个顺序中，首先是i <= gt。如果该测试是False，则{}将“短路”而不评估第二个测试，第二个测试是导致异常的测试。所以：使用while i <= gt and n[i] <= n[lt]:（括号是不必要的，所以我删除了它们，并将这些术语与运算符隔开。有关Python样式的更多建议，请参见PEP 8。）