快速排序算法 (Cormen) 给出了 Stackoverflow

Question

我在算法导论（Cormen，第3版）7.1中实现了给出伪代码的快速排序算法

当我尝试使用小型数组的算法时，结果为真。但是当我尝试使用 N=50000 并且数组已经像这样排序时； N = {1, 2, 3, ..., 50000};

它给出了 WhosebugError。我认为它正在发生，因为该函数将自身递归 50000 次。 QuickSort(A, 0, 49999) => QuickSort(A, 0, 49998) => QuickSort(A, 0, 49997)...继续。

我能解决这个问题吗？或者我应该使用不同的枢轴位置？

这是我的代码；

public void sort(int[] arr){ QuickSort(arr, 0, arr.length - 1); }

private void QuickSort(int[] A, int left, int right){
    if(left < right){
        int index = Partition(A, left, right);
        QuickSort(A, left, index - 1);
        QuickSort(A, index + 1, right);
    }
}

private int Partition(int[] A, int left, int right){
    int pivot = A[right];
    int wall = left-1;
    for(int i=left; i<right; i++){
        if(A[i] <= pivot){
            Swap(A, ++wall, i);
        }
    }
    Swap(A, wall + 1, right);
    return wall + 1;
}

private void Swap(int[] A, int x, int y){
    int keeper = A[x];
    A[x] = A[y];
    A[y] = keeper;
}

Answer 1

是的，这个主元方案不是排序数组的正确选择。正如您所注意到的，它会导致非常不平衡的分区，导致 O(N^2) 复杂度和非常深的递归级别。
有一些方法可以改善这种行为。例如，你可以使用像pivotIdx = start + rand() % (end-start+1);这样的随机索引作为主元，或者选择三中值方法（索引范围内的第一个、最后一个和中间元素的中值）。

P.S。避免堆栈溢出的选项 - 首先为较短的段调用递归，然后为较长的段调用递归。

https://en.wikipedia.org/wiki/Quicksort#Choice_of_pivot

快速排序算法 (Cormen) 给出了 Stackoverflow

Quicksort Algorithm (Cormen) gives Stackoverflow

stack-overflow

algorithm

quicksort