快速排序：更改枢轴元素会导致堆栈溢出

Question

尝试使用Hoare分区方案实现快速排序，但我遇到了一个问题，即无论数组大小如何，更改pivot的索引都会导致溢出。代码：

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）作为轴心元素，这样做很好。但是，将pivot元素更改为任何其他索引都会导致StackOverflow错误，而与正在排序的数组的大小无关。（错误参考第3行，其中调用了partition（））我最好在（min，max）范围内随机选择pivot元素。这是什么原因造成的？

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

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;
}

在一个溢出案例中，我使用了以下方法：

genereateRandomArray(10, 0, 9);

对于一些具体的例子，运行上面的代码，但将pivot元素更改为l[max-1]或l[min 1]，l[min 2]等，会导致StackOverflow。

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

Answer 1

使用pivot的中间值对我来说很有用。下面是一个完整的示例：

    public static 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 static int partition(int[] l, int min, int max){
        int pivot = l[(min+max)/2];
        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;
            }
            int temp = l[i];
            l[i] = l[j];
            l[j] = temp;
        }
    }

    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;
    }

    public static void main(String[] args) {
        int[] A = generateRandomArray(10, 0, 9);
        long bgn, end;
        bgn = System.currentTimeMillis();
        quickSort(A, 0, A.length-1);
        end = System.currentTimeMillis();
        for(int i = 1; i < A.length; i++){
            if(A[i-1] > A[i]){
                System.out.println("failed");
                break;
            }
        }
        System.out.println("milliseconds " + (end-bgn));
    }

Answer 2

我们可以看到，在第一步i变为等于min，枢轴元素与其自身的比较失败，增量不会发生更多：

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

从比较中排除pivot元素（inti=min；），并在最后将其与分区1（似乎是l[j]）交换