如何修复“索引器错误：列表索引超出范围”

Question

我是一个初学者，学习了python和介绍性算法，并试图实现我学到的东西。我正在尝试以下代码，但它反复给我“IndexError:list index out of range”。它在分区函数处失败，特别是在array[0]，array[pivot]=array[pivot]，array[0]代码处。我修不好。感谢任何帮助。在

from math import floor

def mergeSort(a):           # mergesort function
    if len(a)<2:            # if length of a < 2, return a
        return a
    mid=int(len(a)/2)       # mid point
    x=mergeSort(a[:mid])    # recursivly call mergesort for 0 to mid
    y=mergeSort(a[mid:])    # recursivly call mergesort from mid to end
    result=[]               # empty list
    i=j=0                   # initialize i and j
    while j<len(x) and i<len(y):          
        if x[j]<y[i]:          # if x[j] < y[i], then append result for x[j]
            result.append(x[j])
            j+=1               # increment j by 1
        else:
            result.append(y[i])   # append result for y[i]
            i+=1               # increament i by 1
    result+=x[j:]              # add x[j:] --> result
    result+=y[i:]              # add y[i:] --> result
    return result              # return the result

def findMedian(a):               # find the median
    return mergeSort(a)[floor(len(a)/2)]   # call mergesort

def choosePivot(a):               # choose pivot
  medians=[]                      # empty list
  j=0                             # initialize j
  if len(a)==1:                   # if the len = 1, print the element
      print (a[0])
      return a[0]
  if 5<len(a):                    
      medians.append(findMedian(a[0:5]))      # call findMedian for 0 to 5
  else:
      medians.append(findMedian(a))           # call findMedian for a
  for i in range(1,floor(len(a)/5)):         # divide the input array into 5 groups 
      if i*5<len(a):
          medians.append(findMedian(a[j*5:i*5]))   # call findMedian
      else:
          medians.append(findMedian(a[j*5:len(a)]))
  return choosePivot(medians)        # return choosePivot medians

def partition(array,pivot):        # partition
    array[0],array[pivot]=array[pivot],array[0]   #swap
    j=1                  # intiatalize 

    for i in range(1,len(array)): 
        if array[i]<array[0]:
            array[i],array[j-1]=array[j-1],array[i]   #Swap the number less than the pivot
            j+=1

    array[1],array[j]=array[j],array[1]   #swap the pivot to its rightful place
    return j-1,array     #return index of pivot and the partitioned array

def Selection(array,k):         # selection function
    p=choosePivot(array)      

    if k>len(array):        # if k > length of array, then return -1
        print ("Out of array index")
        return -1

    if len(array)>1:             # if len(array) >1, then
        x,b=partition(array,p)           # call partition func
        if x>k:
            c = Selection(b[:x],k)       # search the left half for the statistic
            return c                     # return c
        elif x<k:
            d= Selection(b[x+1:],k-x-1)   # search the right half for the statistic
            return d                      # return d
        else:
            return array[k]               # return the element if statistic is found

    else:
        return array[0]   #Only one element. Only solution, return as it is.
print (Selection([5,1,48,6,2,4,8,7,5,63,2,1,4,8,99],13))

Answer 1

如何修复“索引超出范围”错误？调试。好书：How to debug small programs (#1)。使用print语句或更好的调试器在代码中的特定位置停止并检查出了什么问题。我用visualstudio来做这个。在

红点是一个断点—每当代码碰到红点时，它就会停止执行，我可以随心所欲地检查。我就可以按线路前进了。黄色箭头表示我在哪一行。在

VS可以将变量作为覆盖层固定到源代码上—请参见图像右侧的小片段。在

调试工具列表：https://wiki.python.org/moin/PythonDebuggingTools

---

当您的程序通过VS第三次命中def partition(array,pivot):时，它是越界的：

原因是您的pivot包含value而不是您需要交换它的索引。在

即使您将其修复为：

def partition(array,pivot):        # partition
    idx = array.index(pivot) # get the index of the value here
    array[0],array[idx]=array[idx],array[0]   #swap
    j=1                  # intiatalize 

    for i in range(1,len(array)): 
        if array[i]<array[0]:
            array[i],array[j-1]=array[j-1],array[i]   #Swap the number less than the pivot
            j+=1

    array[1],array[j]=array[j],array[1]   #swap the pivot to its rightful place
    return j-1,array     #return index of pivot and the partitioned array

交换array[1],array[j]=array[j],array[1]时遇到另一个错误，原因是j太大：

你需要修正你的算法。在

高温