我的Python递归快速排序算法运行报错，问题出在哪里？

核心错误点 #

• 第一个错误：partition函数最后交换pivot位置时写死了arr[0]
  每次递归处理的不是整个数组，是数组的某一段（比如第5位到第10位），这一段的第一个元素才是pivot，你写死arr[0]就是每次都把整个数组的第一个元素拿过来交换，完全打乱了分区结果，导致递归永远没法走到l >= h的终止条件，就会一直递归下去，最后触发超出最大递归深度的报错。
• 第二个错误：partition内部的两个内层while循环没有加边界判断
  如果当前处理的段里所有元素都比pivot小/大，那lo +=1或者hi -=1会一直执行，跑到当前段的下标范围外面，这时候访问arr[lo]/arr[hi]就会报索引越界的错误，加边界判断就能避免这个问题。
• 第三个优化点：不需要把数组设为全局变量，可以把数组作为参数传入函数，逻辑更清晰，也能适配不同数组的排序需求。

修复后的完整代码 #

def partition(arr, low, high):
    lo = low
    hi = high
    pivot = arr[lo]  # 取当前子区间第一个元素作为pivot
    while lo < hi:
        # 找左半区第一个大于pivot的元素，加边界防止越界
        while lo <= high and arr[lo] <= pivot:
            lo += 1
        # 找右半区第一个小于等于pivot的元素，加边界防止越界
        while hi >= low and arr[hi] > pivot:
            hi -= 1
        if hi > lo:
            arr[lo], arr[hi] = arr[hi], arr[lo]
    # 把pivot放到正确的分界位置，这里用当前子区间的第一个元素arr[low]，不是arr[0]
    arr[low], arr[hi] = arr[hi], arr[low]
    return hi


def quicksort(arr, l, h):
    if l < h:
        j = partition(arr, l, h)
        quicksort(arr, l, j)
        quicksort(arr, j + 1, h)


# 测试代码
arr = [81, 4, 73, 1, 98, 69, 300, 14, 7, 420, 190, 8, 9]
quicksort(arr, 0, len(arr)-1)  # 用len(arr)-1自动获取最后一个下标，不用手动写12，避免数组长度变了还要改参数
print(arr)

运行结果 #

输出为排序完成的数组：
[1, 4, 7, 8, 9, 14, 69, 73, 81, 98, 190, 300, 420]

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