Java版Quick Sort快速排序执行结果不一致问题求助

你的快速排序代码出现相同输入多次运行结果不一致的核心问题，出在partition函数的逻辑错误，具体有两个关键问题：

1. 未固定pivot位置，遍历中pivot元素被意外交换 #

你通过random选择了随机的pivPoz作为pivot的初始位置，但在后续遍历交换元素的过程中，没有锁定pivot元素的位置。当遍历到某个i位置的元素满足条件时，交换index+1和i的元素，这可能会把原本在pivPoz的pivot元素交换到其他位置，但你仍然用最初的pivPoz来执行最后的交换操作，导致最后放到分区点的不是原来的pivot值，彻底打乱了分区逻辑。

2. 遍历中错误跳过了pivot位置的元素 #

你在遍历的条件中加入了i!=pivPoz，这会导致pivot元素本身在遍历阶段完全不被处理。但pivot元素最终需要被放到分区的正确位置，跳过它会导致前面的分区统计（index的计数）不准确，进一步加剧排序结果的混乱。

核心修复方案 #

正确的随机pivot分区逻辑应该先把pivot元素固定到一个边界位置（比如数组末尾），再进行遍历：

static int partition(int arr[], int lo, int hi){
    // 随机选择pivot位置，先交换到hi位置固定
    int pivPoz = lo + random.nextInt(hi - lo + 1);
    int temp = arr[pivPoz];
    arr[pivPoz] = arr[hi];
    arr[hi] = temp;
    
    int pivot = arr[hi];
    int index = lo - 1;

    // 遍历lo到hi-1，不用再跳过pivot位置（已经在hi）
    for(int i = lo; i < hi; i++){
        if(arr[i] <= pivot){
            index++;
            int a = arr[index];
            arr[index] = arr[i];
            arr[i] = a;
        }
    }

    // 把pivot（在hi）放到正确的分区点
    index++;
    int a = arr[index];
    arr[index] = arr[hi];
    arr[hi] = a;

    return index;
}

这样修改后，pivot元素的位置被固定，遍历逻辑不会再干扰到它，分区结果稳定，多次运行排序结果也会一致。

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