快速排序算法报错：unsupported operand type(s) for -: 'NoneType' and 'int'求助

问题根源 #

你的partition函数存在两个核心问题：

• 返回值逻辑缺失：只有在执行元素交换的else分支时才返回dir，当循环因dir < esq结束时，函数没有返回语句，默认返回None。这导致quickSort中posicao_de_particionamento - 1变成None - 1，触发类型错误。
• 缺少pivot归位步骤：快速排序的partition阶段最后需要将pivot元素与dir位置的元素交换，把pivot放到正确的分割位置，原代码漏掉了这一步，即使修复返回值问题，排序结果也会错误。

修复后的代码 #

def quickSort(dados, inicio, fim):
    if inicio < fim:
        posicao_de_particionamento = partition(dados, inicio, fim)
        quickSort(dados, inicio, posicao_de_particionamento - 1)
        quickSort(dados, posicao_de_particionamento + 1, fim)

def partition(dados, inicio, fim):
    pivo = dados[inicio]
    esq = inicio + 1
    dir = fim
    flag = False
    while not flag:
        while esq <= dir and dados[esq] <= pivo:
            esq = esq + 1
        while dados[dir] >= pivo and dir >= esq:
            dir = dir - 1
        if dir < esq:
            flag = True
        else:
            # 交换左右指针指向的元素
            temp = dados[esq]
            dados[esq] = dados[dir]
            dados[dir] = temp
    # 将pivot交换到正确的分割位置
    dados[inicio] = dados[dir]
    dados[dir] = pivo
    # 统一返回分割位置
    return dir

dados = [50, 51, 98, 85, 60, 66, 72, 33]
quickSort(dados, 0, len(dados) - 1)
print(dados)  # 输出: [33, 50, 51, 60, 66, 72, 85, 98]

关键修改点 #

• 把return dir从else分支移到整个while循环结束后，确保无论循环如何退出，函数都能返回有效的分割位置。
• 在循环结束后添加pivot与dir位置元素的交换操作，完成partition阶段的核心逻辑，确保pivot处于正确的分割点。

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