java - 递归调用溢出堆栈

Question

我在尝试实现快速排序算法时遇到分区问题。我的实现对于大小不超过 10,000 的数组效果很好，但超过这个大小我会收到 StackOverflowError。请注意，只有当输入数组按降序排列时才会发生这种情况。随机排序的数组最多可以达到 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

众所周知，快速排序的最坏情况是 O(n^2)，即当您给它排序输入并选择最差的主元(最高或最低元素)时。正如您所看到的，这也会导致非常深的递归。您不包括枢轴选择机制，因此我无法确定您在做什么，但您似乎选择了最后一个元素。一些谷歌搜索会出现关于 qsort 的枢轴选择的广泛讨论。