自定义Python快速排序偶发数对漏排问题排查

你的代码存在4个核心逻辑错误，是导致偶发局部逆序的根本原因：

• 错误使用list.index()方法定位枢轴：lista.index(x)永远只会返回列表中第一个值等于x的元素下标，只要列表存在重复元素，你拿到的根本不是当前选中枢轴的实际位置；哪怕没有重复元素，每次交换后枢轴位置已经发生变化，循环中反复调用index查询位置，会出现位置判断错位。
• 枢轴位置未同步更新：你每次完成元素和枢轴的交换后，没有记录枢轴移动后的新下标，后续循环的位置判断依然用旧的位置关系，很容易出现两个逆序元素刚好跨过判断边界，没有触发交换逻辑，就会出现你提到的[1,2,3,5,4,6]这类相邻元素逆序的问题。
• 整体逻辑不符合快排分治要求：标准快速排序是选枢轴后把区间拆成小于枢轴、等于枢轴、大于枢轴三个部分，再递归处理左右子区间。你的代码只做了len(lista)次选枢轴遍历，本质是不完整的相邻交换逻辑，没有覆盖所有子区间的排序校验，随机选枢轴时刚好没扫到逆序对就会漏排。
• 存在无效冗余代码：else分支的j = j属于自赋值语句，没有任何实际执行效果，完全可以删除。

错误复现说明 #

当待排序列表为[1,2,3,5,4,6]时，如果随机选枢轴的顺序依次为1、6、3，三次遍历过程中因为index定位枢轴位置错误，5和4的大小关系和位置关系始终没有触发交换条件，最终就会输出错误的排序结果。你在可视化调试时因为固定了首次枢轴选择，刚好避开了触发错位的选轴顺序，所以无法复现问题。

修正参考 #

不要在循环中反复用index查询枢轴位置，选枢轴时直接记录下标，交换后同步更新位置；如果是入门实现，优先用分治逻辑写标准快排，避免位置维护错误：

import random

def quick_sort(lista):
    # 递归终止条件：区间长度小于等于1时已经有序
    if len(lista) <= 1:
        return lista
    # 选枢轴时直接记录下标，不依赖index查询
    pivot_idx = random.randint(0, len(lista) - 1)
    pivot = lista[pivot_idx]
    left, mid, right = [], [], []
    # 按和枢轴的大小关系拆分区间
    for num in lista:
        if num < pivot:
            left.append(num)
        elif num == pivot:
            mid.append(num)
        else:
            right.append(num)
    # 递归处理左右区间后拼接结果
    return quick_sort(left) + mid + quick_sort(right)

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