Python中该quicksort实现为何触发RecursionError？

首先，从你的错误栈和代码来看，触发RecursionError的核心原因是无限递归调用，而导致无限递归的直接问题出在递归调用的范围上。

1. 递归调用的范围错误 #

你错误信息里的代码显示，递归时写了：

array[pivot:] = quicksort(array[pivot:])

但正确的写法应该是针对pivot右侧的子数组（即pivot+1开始的部分）——也就是你提供的代码里原本的正确逻辑：

array[pivot+1:] = quicksort(array[pivot+1:])

当某次分区后pivot的值为0时，array[pivot:]就是整个当前数组，这意味着函数会再次调用自己处理完全相同的数组，形成无限递归循环。每次递归都会消耗栈空间，直到超过Python默认的递归深度限制（默认约1000），最终触发RecursionError。

2. 分区逻辑的附加问题 #

虽然这不是导致本次错误的直接原因，但你的快速排序分区实现还有两个值得注意的点：

• 重复元素处理效率低：当数组中存在大量重复元素时，当前的交换逻辑会做很多无意义的操作（比如交换相同值的元素），影响排序效率。
• 有序数组的递归深度问题：如果固定选择数组最后一个元素作为pivot，当数组已经有序（或逆序）时，递归深度会达到O(n)。对于长度超过1000的数组，即使递归范围正确，也可能触发递归深度超限的错误。

修复建议 #

1. 修正递归调用范围：确保递归时只处理pivot左侧（array[:pivot]）和右侧（array[pivot+1:]）的子数组，不要包含pivot本身——因为pivot已经处于正确的排序位置。
2. 优化分区逻辑：可以采用更高效的双指针分区法，或者选择随机pivot来避免有序数组下的递归深度问题。

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