Python3快速排序无限递归问题求助附代码

嗨，我看了你的代码，确实有几个关键问题导致了无限递归，咱们一步步理清楚：

问题分析 #

1. 列表赋值与引用的误区 #

在partition函数里，你做了lst = lst[1:i] + [pivot] + lst[i:]——这会创建一个新的列表对象，而不是修改传入的原列表。虽然你最后返回了这个新列表，但在quickSort里用lst[l:h], mid = partition(...)的切片赋值看似能修改原列表，但partition返回的mid是基于切片后的子列表的索引，和原列表的索引对应关系完全错了，导致递归的边界永远无法收敛，进而触发无限递归。

2. Pivot分区逻辑的错误 #

你选择lst[0]作为pivot，但后续的分区交换逻辑结束后，把pivot放到正确位置的方式很别扭，还用到了append(float("inf"))再截断的操作，这不仅没必要，还容易引入索引计算的错误，进一步加剧递归边界的问题。

3. 递归终止条件与边界计算错误 #

quickSort里的if l < h-1条件本身没问题，但因为mid的值计算错误（基于子切片的索引而非原列表索引），导致每次递归的l和h永远满足这个条件，无法终止递归。

修正后的代码实现 #

我给你调整成了原地排序的常规快速排序实现，避免切片带来的索引混乱，同时修正了分区逻辑：

def partition(lst, low, high):
    # 选择最后一个元素作为pivot，也可以选中间或者随机元素优化
    pivot = lst[high]
    i = low - 1  # i指向小于pivot的区域最后一个元素
    for j in range(low, high):
        if lst[j] <= pivot:
            i += 1
            lst[i], lst[j] = lst[j], lst[i]
    # 把pivot放到正确的位置
    lst[i+1], lst[high] = lst[high], lst[i+1]
    return i + 1  # 返回pivot在原列表中的索引

def quickSort(lst, low, high):
    if low < high:
        pi = partition(lst, low, high)
        # 递归排序pivot左右的子列表
        quickSort(lst, low, pi - 1)
        quickSort(lst, pi + 1, high)

lst1 = [10, 12, 8, 16, 2, 6, 3, 9, 5]
quickSort(lst1, 0, len(lst1)-1)
print(lst1)  # 输出: [2, 3, 5, 6, 8, 9, 10, 12, 16]

关键修改点说明 #

• 原地分区：不再创建新列表，直接在原列表上交换元素，索引计算更清晰，避免引用混乱。
• 清晰的pivot定位：用经典的分区逻辑，最后把pivot放到正确位置，返回的索引直接对应原列表的位置，递归边界计算准确。
• 正确的递归终止条件：当low >= high时终止递归，确保每次递归的子问题规模都在缩小，不会无限递归。

如果你想保留你原来的pivot选择方式（选第一个元素），也可以调整partition函数——先把pivot和最后一个元素交换，再用上面的逻辑，这样能避免极端情况（比如已排序的列表）导致的时间复杂度退化。

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