Python 3.6原地快速排序超36元素时递归崩溃排查求助

嘿，我看到你在实现原地快速排序时遇到了递归崩溃的问题——36个元素以内正常，37个及以上就无限递归，这确实挺头疼的。咱们来揪出问题根源，然后修复它～

核心问题：分区逻辑存在致命缺陷 #

你的代码里，分区（Partition）阶段的while循环逻辑完全错误，这是导致无限递归的直接原因。来看这段代码：

while(start!=end):
    if(array[start]>pivot):
        if(pivotposition==end):
            pivotposition = start
            temp = array[start]
            array[start] = array[end]
            array[end] = temp
            end = end -1
        else:
            start = start + 1

这里的问题非常明显：当array[start] <= pivot时，你没有任何代码让start指针移动。比如，当你把pivot固定在begin位置时，start初始就是begin，此时array[start]等于pivot，不会进入if分支，start就一直停在原地，end也不动，while(start!=end)循环永远不会退出，直接导致无限循环，最终递归栈溢出。

那为什么36个元素时好像能运行？纯粹是巧合——可能你的测试数组在长度较小时，所有递归分支都触发了final-begin<=1的条件，跳过了这个有问题的while循环。但数组一旦变长，必然会进入这个错误的分区逻辑，直接卡死。

修复方案：正确实现原地分区逻辑 #

原地快速排序的核心是正确的分区：用左右指针分别从两端向中间移动，交换不符合条件的元素，最后把pivot放到正确的位置。我修改了你的代码，修复了所有问题：

def quicksort(array, begin, final, o):
    # 递归终止条件：子数组长度<=1时直接返回
    if final <= begin:
        return
    
    # 随机选择pivot，避免数组有序时的最坏情况（O(n²)时间+栈溢出）
    import random
    pivot_idx = random.randint(begin, final)
    # 把pivot交换到子数组末尾，方便后续处理
    array[pivot_idx], array[final] = array[final], array[pivot_idx]
    pivot = array[final]
    
    left = begin
    right = final - 1

    # 左右指针移动，完成分区
    while left <= right:
        # 从左往右找第一个大于pivot的元素
        while left <= right and array[left] <= pivot:
            left += 1
        # 从右往左找第一个小于等于pivot的元素
        while left <= right and array[right] > pivot:
            right -= 1
        # 如果指针还没相遇，交换两个元素
        if left < right:
            array[left], array[right] = array[right], array[left]
    
    # 把pivot放到正确的位置（left指针的位置就是pivot的最终位置）
    array[left], array[final] = array[final], array[left]
    
    # 调试用的递归深度打印
    print(o)
    
    # 递归处理左右两个子数组
    quicksort(array, begin, left - 1, o + 1)
    quicksort(array, left + 1, final, o + 1)

# 测试代码
randomnumbers = [160,51,77,32,53,44,83,116,128,170,190,192,192,117,28,32,9,17,136,146,47,67,20,196,41,122,17,13,11,176,198,79,166,71,114,44,116]
print("排序前:", randomnumbers)
quicksort(randomnumbers, 0, len(randomnumbers)-1, 0)
print("排序后:", randomnumbers)
input("press Enter")

关键修改点说明 #

1. 修正递归终止条件：直接判断final <= begin，更简洁严谨，避免之前的分支判断遗漏。
2. 随机选择pivot：避免数组已经有序时，每次选第一个元素作为pivot导致的最坏情况（递归深度达到n，直接栈溢出）。
3. 正确的分区逻辑：用左右指针配合，分别寻找需要交换的元素，确保循环能正常退出，分区完成后把pivot放到正确位置。
4. 移除冗余代码：删除了原代码中逻辑混乱的pivotposition变量和冗余的交换逻辑。

现在你可以测试修改后的代码，不管是36个还是37个元素，甚至更大的数组，都能正常完成排序，不会再出现无限递归崩溃的问题～

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