以首、中、尾元素中位数为基准的快速排序实现异常求助

代码中的核心问题 #

• 缺少依赖模块：使用random.sample但未导入random模块，直接运行会触发报错。
• 分区循环条件错误：第一个内层while循环用inicio < len(n)作为判断条件，会导致指针遍历到当前分区外的元素，破坏排序逻辑，应该限制在inicio <= fim范围内。
• pivot索引判断逻辑漏洞：三个独立的if语句在存在重复元素时，会错误覆盖indice_pivot的值，应该改用elif链式判断，确保只匹配一次。
• 双指针移动逻辑混乱：原代码中直接修改传入的inicio参数，结合错误的循环条件，会导致指针移动超出预期分区范围，最终导致pivot位置交换错误。

修正后的完整代码 #

import random
from sys import stdin, stdout

def readln(): 
    return stdin.readline().rstrip()

def outln(n): 
    stdout.write(str(n))
    stdout.write("\n")

m = 10 
n = random.sample(range(1, 1000000), m)

def particao(n, inicio, fim): 
    # 三数取中确定基准值及初始索引
    primeiro = n[inicio]
    pos_meio = (inicio + fim) // 2
    meio = n[pos_meio]
    ultimo = n[fim]
    
    # 通过逻辑判断直接找出中位数，避免排序小列表
    if (primeiro > meio) != (primeiro > ultimo):
        pivot = primeiro
        indice_pivot = inicio
    elif (meio > primeiro) != (meio > ultimo):
        pivot = meio
        indice_pivot = pos_meio
    else:
        pivot = ultimo
        indice_pivot = fim

    # 先将基准值交换到分区末尾，简化后续遍历逻辑
    n[indice_pivot], n[fim] = n[fim], n[indice_pivot]
    pivot = n[fim]
    # 记录小于等于基准值的元素边界
    left_bound = inicio - 1

    # 遍历分区内元素，将小于等于基准的元素移到左半区
    for current in range(inicio, fim):
        if n[current] <= pivot:
            left_bound += 1
            n[left_bound], n[current] = n[current], n[left_bound]
    
    # 将基准值移到正确的中间位置
    n[left_bound + 1], n[fim] = n[fim], n[left_bound + 1]
    return left_bound + 1

def quicksort(n, inicio, fim): 
    if inicio < fim: 
        part = particao(n, inicio, fim) 
        quicksort(n, inicio, part - 1) 
        quicksort(n, part + 1, fim)

quicksort(n, 0, len(n)-1) 
print(n)

修正说明 #

1. 补全random模块导入，解决基础运行错误。
2. 优化三数取中的判断逻辑，不用额外生成小列表再排序，直接通过比较找出中位数，同时避免重复元素导致的索引覆盖问题。
3. 调整分区逻辑：先把基准值移到分区末尾，再用单指针遍历交换的方式整理元素，逻辑更清晰，彻底避免原双指针移动的条件错误。
4. 严格限制操作范围在当前分区内，确保不会干扰其他分区的元素，支持1000+元素的排序场景。

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