java - QuickSort:更改枢轴元素会导致 StackOverflow

Question

尝试使用 Hoare 分区方案实现 QuickSort，但我遇到了一个问题，无论数组大小如何，更改数据透视表的索引都会导致溢出。代码:

public void quickSort(int[] l, int min, int max){
    if (min < max){
        int p = partition(l, min, max);
        quickSort(l, min, p);
        quickSort(l, p+1, max);
    }
}
public int partition(int[] l, int min, int max){
    int pivot = l[min];
    int i = min - 1;
    int j = max +1;
    while(true){
        do{
            i++;
        }while(l[i] < pivot);
        do{
            j--;
        }while(l[j] > pivot);

        if (i >= j) {
                return j;
        }
        //Swap
        int temp = l[i];
        l[i] = l[j];
        l[j] = temp;
    }

}

此实现选择低索引(此处命名为 min)作为基准元素，并且效果很好。但是，将枢轴元素更改为任何其他索引都会导致 StackOverflow 错误，而不管正在排序的数组的大小如何。 (错误指的是第 3 行，其中调用了 partition())我最好在 (min,max) 范围内随机选择主元元素。这是什么原因造成的？

编辑: 使用的数组生成如下:

public static int[] generateRandomArray(int size, int lower, int upper){
    int[] random = new int[size];
    for (int i = 0; i < random.length; i++) {
        int randInt = ThreadLocalRandom.current().nextInt(lower, upper+1);
        random[i] = randInt;
    }
    return random;
}

在其中一个 Overflow 案例中，我使用了这个:

genereateRandomArray(10, 0, 9);

对于一些具体的例子，运行上面的代码但改变枢轴元素说，l[max-1] 或 l[min+1]，l[min+2] 等在我这边给出了 StackOverflow。

我的问题的解决方案正如用户 MBo 指出的那样，将枢轴元素交换到数组的第一个索引，因为算法本身依赖于索引 0 上的枢轴。这是我忽略的。 (int i = min - 1; 然而是正确的，并且保持这种状态。)

Answer 1

我们可以看到在第一步i变得等于min，主元元素与自身的比较失败并且没有发生自增:

int pivot = l[min];
    int i = min - 1;
...
 do{
            i++;
        }while(l[i] < pivot);

从比较中排除枢轴元素(int i = min;)并在最后与分区一(似乎是 l[j])交换