递归调用溢出堆栈

Question

我在尝试实施快速排序算法时遇到分区问题。我的实现适用于大小不超过 10,000 的数组，但超过该数组时我会收到 WhosebugError。请注意，这仅在输入数组处于 a/descending 顺序时才会发生。随机排序的数组最多可达 10,000,000,000，才会导致同样的问题。

我很确定我对数组进行分区时的部分有问题，但我真的看不出有什么问题。我试过调试但没有成功找到问题。我知道这个错误是由太多的递归调用引起的，但据我所知，如果分区实施得当，堆栈应该不会溢出。

提前致谢:)

我的代码：

public void sort(int[] v, int first, int last) {


    if (first >= last) return; 
    //less than two elements left in subvector

    // Partition the elements so that every number of
    // v[first..mid] <= p and every number of v[mid+1..last] > p.
    int[]subvector = new int[2];

    subvector = partition(v, first, last);

    sort(v, first, subvector[0]-1);
    sort(v, subvector[1], last);

}

以及分区方式：

private int[] partition(int[] v, int first, int last) {
    int low = first;
    int mid = first;
    int high = last;
    int pivot = getPivot(v, last);


    while (mid <= high) {
        // Invariant:
        //  - v[first..low-1] < pivot
        //  - v[low..mid-1] = pivot
        //  - v[mid..high] are unknown
        //  - v[high+1..last] > pivot
        //
        //       < pivot   = pivot      unknown     > pivot
        //     -----------------------------------------------
        // v: |          |          |a            |           |
        //     -----------------------------------------------
        //     ^          ^          ^           ^           ^
        //    first      low        mid         high        last
        //
        int a = v[mid];
        if (a < pivot) {
            v[mid] = v[low];
            v[low] = a;
            low++;
            mid++;
        } else if (a == pivot) {
            mid++;
        } else { // a > pivot
            v[mid] = v[high];
            v[high] = a;
            high--;
        }
    }

    return new int[]{low, high};
}

Answer 1

Quicksort 已知是 O(n^2) 最坏情况，即当您给它排序输入并选择最差的主元（最高或最低元素）时。如您所见，这也会导致非常深的递归。你没有包含你的枢轴 selection 机制，所以我不能确定你在做什么，但你似乎 select 最后一个元素。一些谷歌搜索会出现关于 pivot selection for qsort 的广泛讨论。

递归调用溢出堆栈

Recursion calls overflows stack

java

arrays

recursion

quicksort