Python Quick Sort快速排序未全量排序，疑似partition函数有误

问题拆解 #

• 基准元素未归位
  你编写的分区逻辑全程没有将存放在lower_bound位置的pivot元素，交换到最终的分界点位置，导致pivot始终留在数组开头，根本没有达成“小于pivot的元素在左、大于pivot的元素在右”的分区目标。
• 末尾交换逻辑完全无效
  外层while start < end循环退出时，start和end已经处于交叉状态，此时end指向的位置就是正确的分界索引。你代码里写的arr[start], arr[end] = arr[end], arr[start]属于冗余自交换：当start和end交叉时，两个位置的元素本就处于符合分区要求的顺序，这步交换没有实际作用，更没有把pivot放到正确位置。

修正方案 #

按照Hoare分区的标准流程，在循环退出、确定分界点end后，必须执行一步关键交换：将存放在lower_bound的pivot元素与arr[end]互换，让pivot落在最终的正确排序位置上。

修正后的partition函数代码 #

def partition(arr, lower_bound, upper_bound):
    pivot = arr[lower_bound]
    start = lower_bound
    end = upper_bound

    while start < end:
        while start <= end and arr[start] <= pivot:
            start += 1
        while start <= end and arr[end] >= pivot:
            end -= 1
        if start < end:
            arr[start], arr[end] = arr[end], arr[start]
    
    # 替换原代码的错误自交换逻辑
    arr[lower_bound], arr[end] = arr[end], arr[lower_bound]
    return end

补充：原quickSort函数中if lower_bound < upper_bound的判断属于冗余逻辑——因为前面已经对lower_bound >= upper_bound的情况做了直接返回，剩下的执行路径必然满足lower_bound < upper_bound，可以直接去掉这层判断，简化代码。

修正后运行完整快速排序代码，会输出正确的全排序结果[1, 2, 5, 6, 7, 7, 9, 10, 15]。

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