大输入上的java快速排序堆栈溢出

Question

如果我给出反向排序数组，我的快速排序实现会导致StackOverflow错误。对于大约1000个项目，它可以正常工作，但是对于10000个以上的项目，我得到了StackOverflow错误。如果我得到这个错误，递归深度大约是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?

你能做的就是把你的方法，从一个递归的方法变成一个迭代的方法。有几种方法可以做到这一点。我在网上找到了几个例子：

• http://www.geeksforgeeks.org/iterative-quick-sort/
• http://kosbie.net/cmu/summer-08/15-100/handouts/IterativeQuickSort.java

Answer 2

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

• 每次都可以将较大的分区放在堆栈上，在较小的分区先排序时将其留在那里。这样可以防止太多的小分区同时阻塞堆栈

• 您可以使用另一种方法，例如插入排序，对小分区进行排序，而不是快速排序。同样，这使得许多小分区远离堆栈。您可以进行实验，但15-20个元素区域中的某个元素通常算作“小”分区

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