QuickSort能够堆栈溢出吗？

Question

在我的代码中,该方法将调用自身(递归).我们知道,深度方法调用会导致堆栈溢出.那么,当存在大量数据时,是否会发生堆栈溢出？

我的QuickSort代码:(排序类的内部类)

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);
    }
}

Answer 1

递归的深度以及快速排序的持续时间取决于数据点的相对顺序以及数据点的数量.如果枢轴点总是最终成为数据的最大或最小成员,那么您在上面的代码上递归将递归到与数据大小一样深的位置.

使用quicksort,您可以确保递归深度很小,即使它仍然需要很长时间.这在http://en.wikipedia.org/wiki/Quicksort中简要讨论如下:

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

非常简单,这意味着你首先要重写

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

如

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

(使用while循环将参数修改为f,以便第二次递归调用对应于while循环的第二次传递).

然后你看一下如何为两个递归调用拆分数组,并确保第二个递归调用 - 转换为while循环 - 用于数组的较大一半.这意味着剩余的递归调用总是不超过数组的一半,这意味着你永远不会超过数组大小的log base 2.