QuickSort：更改枢轴元素会导致 StackOverflow

Question

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

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）作为基准元素，效果很好。但是，将枢轴元素更改为任何其他索引都会导致 Whosebug 错误，而不管正在排序的数组的大小如何。（错误指的是第 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;
}

在其中一个溢出案例中，我使用了这个：

genereateRandomArray(10, 0, 9);

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

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

Answer 1

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

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

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

Answer 2

使用中心值的中间值对我有用。这是一个完整的例子：

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

QuickSort：更改枢轴元素会导致 StackOverflow

QuickSort: Changing pivot element causes StackOverflow

java

stack-overflow

algorithm

quicksort