Python快速排序算法出现IndexError索引越界问题求助

问题说明 #

我在Python中实现了快速排序算法，运行时遇到无法解决的索引越界错误（IndexError），以下是我的代码、控制台输出及报错信息，需要协助排查修复。

原始实现代码 #

arr = [5,3,2,6,1,2,3,0,4]

def quicksort(arr,low,high):
    pv = high
    pivot = arr[pv]
    high-=1
    while low<high:
        print("high=",high,"pv=", pv,"low=",low)
        print(arr)
        while arr[low]<pivot:
            low+=1
            print("high=",high,"pv=", pv,"low=",low)
            print(arr)
        while arr[high]>pivot and high>low:
            high-=1
            print("high=",high,"pv=", pv,"low=",low)
            print(arr)
        arr[high],arr[low] = arr[low], arr[high]
    
    arr[pv],arr[high] = arr[high],arr[pv]
    return quicksort(arr,0,high-1)
    return quicksort(arr,high+1,len(arr)-1)

quicksort(arr,0,8)

控制台输出 #

high= 7 pv= 8 low= 0
[5, 3, 2, 6, 1, 2, 3, 0, 4]
high= 7 pv= 8 low= 0
[0, 3, 2, 6, 1, 2, 3, 5, 4]
high= 7 pv= 8 low= 1
[0, 3, 2, 6, 1, 2, 3, 5, 4]
high= 7 pv= 8 low= 2
[0, 3, 2, 6, 1, 2, 3, 5, 4]
high= 7 pv= 8 low= 3
[0, 3, 2, 6, 1, 2, 3, 5, 4]
high= 6 pv= 8 low= 3
[0, 3, 2, 6, 1, 2, 3, 5, 4]
high= 6 pv= 8 low= 3
[0, 3, 2, 3, 1, 2, 6, 5, 4]
high= 6 pv= 8 low= 4
[0, 3, 2, 3, 1, 2, 6, 5, 4]
high= 6 pv= 8 low= 5
[0, 3, 2, 3, 1, 2, 6, 5, 4]
high= 6 pv= 8 low= 6
[0, 3, 2, 3, 1, 2, 6, 5, 4]
high= 4 pv= 5 low= 0
[0, 3, 2, 3, 1, 2, 4, 5, 6]
high= 4 pv= 5 low= 1
[0, 3, 2, 3, 1, 2, 4, 5, 6]
high= 4 pv= 5 low= 1
[0, 1, 2, 3, 3, 2, 4, 5, 6]
high= 4 pv= 5 low= 2
[0, 1, 2, 3, 3, 2, 4, 5, 6]
high= 3 pv= 5 low= 2
[0, 1, 2, 3, 3, 2, 4, 5, 6]
high= 2 pv= 5 low= 2
[0, 1, 2, 3, 3, 2, 4, 5, 6]

报错信息 #

Traceback (most recent call last):
  File "<ipython-input-42-895bbee6df57>", line 28, in <module>
    quicksort(arr,0,8)
  File "<ipython-input-42-895bbee6df57>", line 23, in quicksort
    return quicksort(arr,0,high-1)
  File "<ipython-input-42-895bbee6df57>", line 23, in quicksort
    return quicksort(arr,0,high-1)
  File "<ipython-input-42-895bbee6df57>", line 23, in quicksort
    return quicksort(arr,0,high-1)
  File "<ipython-input-42-895bbee6df57>", line 23, in quicksort
    return quicksort(arr,0,high-1)
  File "<ipython-input-42-895bbee6df57>", line 23, in quicksort
    return quicksort(arr,0,high-1)
  File "<ipython-input-42-895bbee6df57>", line 23, in quicksort
    return quicksort(arr,0,high-1)
  File "<ipython-input-42-895bbee6df57>", line 23, in quicksort
    return quicksort(arr,0,high-1)
  File "<ipython-input-42-895bbee6df57>", line 22, in quicksort
    arr[pv],arr[high] = arr[high],arr[pv]
IndexError: list index out of range

问题分析与修复 #

核心问题点 #

1. 缺少递归终止条件：当low >= high时，当前子数组只有一个元素或为空，无需排序，但原代码会继续执行后续逻辑，导致无限递归，最终high变为负数，访问数组时越界。
2. 无效的return语句：第一个return quicksort(...)执行后，第二个return永远不会被触发，右侧子数组从未被排序。
3. 循环边界未校验：内层while arr[low] < pivot没有判断low <= high，可能导致low超过high后继续访问数组，引发越界。

修正后的代码 #

arr = [5,3,2,6,1,2,3,0,4]

def quicksort(arr, low, high):
    # 递归终止条件：子数组无需排序
    if low >= high:
        return
    
    pv = high
    pivot = arr[pv]
    left = low
    right = high - 1
    
    while left < right:
        # 左指针右移，直到找到大于等于pivot的元素，同时避免越界
        while left <= right and arr[left] < pivot:
            left += 1
        # 右指针左移，直到找到小于等于pivot的元素，同时避免越界
        while left <= right and arr[right] > pivot:
            right -= 1
        # 交换左右指针元素，仅当left < right时执行
        if left < right:
            arr[left], arr[right] = arr[right], arr[left]
    
    # 将pivot放到正确位置
    arr[pv], arr[left] = arr[left], arr[pv]
    
    # 递归排序左右子数组
    quicksort(arr, low, left - 1)
    quicksort(arr, left + 1, high)

quicksort(arr, 0, len(arr)-1)
print("排序结果:", arr)

关键修改说明 #

• 添加if low >= high: return作为递归终止条件，避免无限递归和越界。
• 重命名变量low/high为left/right，避免和函数参数的low/high混淆，同时保留原参数用于递归。
• 内层循环添加left <= right的边界校验，防止指针越界。
• 移除无效的return语句，直接调用两次递归分别处理左右子数组。
• 交换pivot时使用left指针（此时left和right重合），确保位置正确。

内容的提问来源于stack exchange，提问作者Snehal Majumder