快速排序中的堆栈溢出

Question

如果我尝试使用numbers.length n = 100.000(".(和数字倒序的代码，我会得到一个Stackoverflow，所以像100.000 99.999 99.998 ...这正常吗？它适用于较小的 n，例如 10.000。

private void quickSort(int[] numbers, int l, int r) {
if (l < r) {
int p = numbers[r];
int i = l - 1;
int j = r;
do {
do {
i++;
} while (numbers[i] < p);
do {
j--;
} while (j >= l && numbers[j] > p);
if (i < j) {
swap(numbers, i, j);
}
} while (i < j);
swap(numbers, i, r);
quickSort(numbers, l, i - 1);
quickSort(numbers, i + 1, r);
}
}

Answer 1

您可能进行了太多的递归调用，因为数组已经排序。您可以允许 JVM 占用更多内存或更改最大递归深度。更好的解决方案是实现非递归快速排序。下面是一个 Java 示例。