大输入时 QuickSort 堆栈溢出

Question

如果我给出反向排序的数组，我的 QuickSort 实现会导致 Whosebug 错误。它适用于大约 1000 个项目，但对于 10000+ 个项目，我收到 Whosebug 错误。如果我得到错误，递归深度约为 9000。我知道我的算法总是选择子数组的最新元素作为基准，这不是最优的，但我不会改变它，因为我想让它像这样工作。这是代码：

private int partition(int[] numbers, int begin, int end) {
    int pivot = numbers[end];
    int partitionIndex = begin;
    for (int i = begin; i < end; ++i) {
        comparisonCounter++;
        if (numbers[i] <= pivot) {
            if (i != partitionIndex) {
                swapCounter++;
                int temp = numbers[i];
                numbers[i] = numbers[partitionIndex];
                numbers[partitionIndex] = temp;
            }
            partitionIndex++;
        }
    }
    if (partitionIndex != end) {
        swapCounter++;
        int temp = numbers[partitionIndex];
        numbers[partitionIndex] = numbers[end];
        numbers[end] = temp;
    }
    return partitionIndex;
}

private void quickSort(int[] numbers, int begin, int end) {
    if (begin < end) {
        int partitionIndex = partition(numbers, begin, end);
        quickSort(numbers, begin, partitionIndex - 1);
        quickSort(numbers, partitionIndex + 1, end);
    }
}

我的实现有问题吗？我该如何解决？谢谢！

Answer 1

您的代码似乎没有任何问题，但请记住，这是一个递归函数，并且大多数语言都有一个深度有限的堆栈，如果您的输入足够大，您一定会到达该堆栈。对于 Java，请参阅：

What is the maximum depth of the java call stack?
How to predict the maximum call depth of a recursive method?

您可以做的是将您的方法从递归方法转变为迭代方法。有几种方法可以做到这一点。我刚刚在网上找到了几个例子：

Answer 2

有一些方法可以减少快速排序中的堆栈大小。

您可以每次都将较大的分区放在堆栈上，将其留在堆栈中，而较小的分区首先排序。这样可以防止过多的小分区一次堵塞堆栈。
您可以使用其他方法（例如插入排序）来对小分区进行排序，而不是使用快速排序。同样，这使许多小分区远离堆栈。您可以进行试验，但 15 - 20 个元素的区域通常算作一个 "small" 分区。

正如您所说，使用更好的方法来选择您的支点也会有所帮助。

大输入时 QuickSort 堆栈溢出

QuickSort stack overflow on big input

java

stack-overflow

quicksort