How to fix 'IndexError: list index out of range' error

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])    # recursively call mergesort for 0 to mid
    y=mergeSort(a[mid:])    # recursively 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               # increment 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

如何修复 "index out of range" 错误？调试。伟大的阅读：How to debug small programs (#1)。使用打印语句或更好的调试器在代码中的某些位置停止并检查出了什么问题。为此，我使用 Visual Studio。

红点是一个断点 - 只要代码碰到红点就会停止执行，我可以尽情地检查。然后我可以提前line-wise。黄色箭头表示我在哪一行。

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

由于 j 太大，您运行在交换 array[1],array[j]=array[j],array[1] 时陷入另一个错误：

你需要修正你的算法。

HTH

How to fix 'IndexError: list index out of range' error

How to fix 'IndexError: list index out of range' error

python

mergesort

partitioning

python-3.x