Quicksort实现Bug排查：算法逻辑缺陷分析与最小修复方案咨询

问题现象 #

该快速排序实现可通过多数测试用例，但在测试用例[5,71,1,91,10,2,0,0,13,45,7]中失败，输出结果为[0,0,1,2,5,10,7,71,13,45,91]，与预期的[0,0,1,2,5,7,10,13,45,71,91]不符，核心问题是10与7的顺序颠倒。

逻辑缺陷分析 #

问题根源出在partition函数的两处逻辑错误：

1. 左指针移动的边界条件错误 #

第一个内层循环while(head < hi && nums[head] < pivot) ++head;使用head < hi作为边界，导致左指针head最多只能移动到hi-1的位置，无法检查最后一个元素nums[hi]是否小于基准值pivot。这会导致循环结束后，head的位置可能没有指向最后一个需要与pivot比较的元素，进而影响后续基准值的交换逻辑。

2. 基准值位置返回错误 #

循环结束后，代码根据nums[head]与pivot的大小，将基准值pivot交换到head或head-1的位置，但始终返回head作为基准值的索引。这会导致递归划分区间时出现偏差：当基准值实际被放到head-1位置时，返回的head会让右区间的起始位置多了1，遗漏了head位置的元素（比如测试用例中的10），该元素无法进入后续排序流程，最终导致顺序错误。

最小改动修复方案 #

只需修改partition函数的两处逻辑：

1. 将左指针移动的边界条件从head < hi改为head <= hi，确保能检查到所有元素；
2. 根据基准值的实际交换位置，返回对应的索引（而非固定返回head）。

修复后的partition代码如下：

private int partition(int[] nums, int lo, int hi){
    int pivot = nums[lo];
    int head = lo + 1;
    int tail = hi;
    while(head < tail){
        // 修复：将head < hi改为head <= hi
        while(head <= hi && nums[head] < pivot) ++head;
        while(nums[tail] > pivot) --tail;
        if(head < tail){
            swap(nums, head, tail);
            ++head;
            --tail;
        }
    }
    int pivotPos;
    if(nums[head] < pivot){
        swap(nums, lo, head);
        pivotPos = head;
    } else {
        swap(nums, lo, head - 1);
        pivotPos = head - 1;
    }
    // 修复：返回基准值实际所在的位置
    return pivotPos;
}

验证 #

修复后，测试用例[5,71,1,91,10,2,0,0,13,45,7]会被正确排序为预期结果，同时原有的其他测试用例也能正常通过。

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