随机快速排序（randomized quick sort）基准分支偶发失效问题

你遇到的偶发无序问题，核心是两个逻辑错误：

1. 子数组长度判断错误 #

你混淆了索引差值和实际元素个数：

• e - s == 1 对应的是2个元素的子数组（索引s和e）
• e - s == 2 对应的是3个元素的子数组（索引s、s+1、e）

当处理3个元素的子数组时，partition只能将pivot放到正确位置，但pivot左右的子数组（比如右侧的两个逆序元素）并不会自动有序。你直接return跳过了递归处理，这部分无序元素就会留在最终数组里，导致偶发错误。

2. 短数组处理逻辑错误 #

即便对于2个元素的子数组，直接调用partition虽然多数情况能排好序，但依赖固定选第一个元素当pivot的逻辑；而3个元素的场景下，partition完成后必然存在未处理的子数组，不递归就会留下无序隐患。

修复方案 #

把原来的短数组判断逻辑替换成对长度<=2的子数组直接做简单交换排序，避免依赖partition且跳过递归的问题：

import random

def quickSort(arr,s,e):
    if s >= e: return 
    # 处理长度为1或2的子数组
    if e - s <= 1:
        if arr[s] > arr[e]:
            arr[s], arr[e] = arr[e], arr[s]
        return    
    x = randPartition (arr,s,e)
    quickSort(arr,s,x-1)
    quickSort(arr,x+1,e)
        
def partition(arr,s,e):
    pivot = arr[s]
    x = s
    for i in range (s+1,e+1):
        if arr[i] < pivot :
            x+=1
            arr[x],arr[i]=arr[i],arr[x]
    arr[s],arr[x] = arr[x],arr[s]
    return x 

def randPartition(arr,s,e):
    x = random.randint(s,e)
    arr[x],arr[s] = arr[s],arr[x]
    return partition(arr,s,e)

arr = [1,5,0,3,-15,12,96,99,1500,-1500,66,120]
quickSort(arr,0,len(arr)-1)
print(arr)

这样修改后，无论随机选pivot的结果如何，短数组都会被正确排序，不会再出现偶发无序的情况。

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