Python快速排序（Quick_sort）代码排序异常问题求助

你的快速排序问题确实出在Partition函数的交换逻辑上，我们直接拆解问题并给出修正方案：

原代码核心问题 #

当i == j时直接交换A[l]和A[i-1]的逻辑完全错误：

• 循环结束时i与j重合位置的元素，和基准值x的大小关系无明确保证
• 错误地将基准值放到i-1位置，导致基准值的分区位置彻底偏离，后续递归排序完全失效

修正后的完整代码 #

def Partition(A, l, r):
    x = A[l]  # 取左端点作为基准值
    i = l + 1
    j = r
    while True:
        # 从左往右找第一个 >= 基准值的元素
        while i <= r and A[i] < x:
            i += 1
        # 从右往左找第一个 <= 基准值的元素
        while j >= l and A[j] > x:
            j -= 1
        if i > j:
            break
        # 交换元素，让小值去左、大值去右
        A[i], A[j] = A[j], A[i]
        i += 1
        j -= 1
    # 将基准值放到正确的分区位置（j是最后一个 <= 基准值的位置）
    A[l], A[j] = A[j], A[l]
    return j


def Quick_sort(A, l, r):
    if l < r:
        P = Partition(A, l, r)
        Quick_sort(A, l, P - 1)
        Quick_sort(A, P + 1, r)

关键修正点说明 #

1. 调整循环终止条件：只有当i > j时才退出循环，避免提前处理未完成的指针移动
2. 修正指针移动逻辑：去掉i < j、j > i的限制，确保指针能遍历到数组边界，不会遗漏元素
3. 基准值归位逻辑：将基准值与j位置元素交换，j是最后一个小于等于基准值的位置，保证分区后左边全是<=基准值的元素，右边全是>=基准值的元素
4. 返回正确分区点：返回j作为分区基准点，后续递归排序其左右区间

测试验证 #

用你的测试列表C = [40, 10, 30, 20]测试：

1. 第一次分区后数组变为[20, 10, 30, 40]，分区点P=0
2. 递归排序右区间[1,3]，分区后数组调整为[20,10,30,40]→[10,20,30,40]
3. 最终得到正确排序结果

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