0

在我的代码中，该方法将调用自身（递归）。我们知道，深度方法调用会导致堆栈溢出。那么，当数据量很大时，会不会发生栈溢出呢？

我的快速排序代码：（排序类的内部类）

private static class QuickSortor extends Sortor {

    protected <E> void sort(E[] a, boolean isAsc) {
        quickSort(a, 0, a.length - 1, isAsc);
    }

    private <E> void quickSort(E[] a, int left, int right, boolean isAsc) {
        if (left >= right)
            return;
        int middle = left;
        Comparable<E> cmp = (Comparable<E>) a[left];
        for (int i = left + 1; i <= right; i++) {
            int result = cmp.compareTo(a[i]);
            if (!isAsc)
                result = -result;
            if (result >= 0)
                swap(a, ++middle, i);
        }
        swap(a, left, middle);
        quickSort(a, left, middle - 1, isAsc);
        quickSort(a, middle + 1, right, isAsc);
    }
}
4

2 回答 2

5

递归的深度以及快速排序需要多长时间，取决于数据点的相对顺序以及数据点的数量。如果枢轴点总是最终成为您在上面的代码中递归的数据的最大或最小成员，那么递归将与数据大小一样深。

使用快速排序，您可以确保递归深度很小，即使最终仍然需要很长时间。这在http://en.wikipedia.org/wiki/Quicksort中进行了非常简短的讨论，如下所示：

为了确保最多使用 O(log N) 空间，首先递归到数组的较小一半，然后使用尾调用递归到另一个。

很简单，这意味着你首先要重写

f(...)
{
  ...
  f()
  f()
}

作为

f()
{
  while (...)
  {
    ...
    f()
    ...
 }
}

（使用 while 循环修改 f 的参数，以便第二次递归调用对应于 while 循环的第二次循环）。

然后查看如何为两个递归调用拆分数组，并确保第二个递归调用（变成 while 循环）用于数组的较大一半。这意味着剩余的递归调用总是不超过数组的一半，这意味着你永远不会比数组大小的 log base 2 更深。

于 2012-06-20T04:00:45.720 回答
2

您编写的算法总是选择最左边的元素作为枢轴。如果在已经排序的数组上执行，这将表现出快速排序的病态O(n^2)行为，这将导致非常小的数组发生堆栈溢出。

Integers您可以通过对从 0 到 15000 的数字数组依次调用排序来进行尝试。我得到一个StackOverflowError尝试。在 15000 个随机数的数组上执行它Integer不会导致堆栈溢出。

于 2012-06-20T04:12:25.433 回答