java为什么快速排序使用O（log（n））额外空间？

Question

我已经实现了下面的快速排序算法。我在网上读到，它的空间要求是O（log（n））。为什么会这样？我不会创建任何额外的数据结构

是因为我的递归会占用堆栈上的一些额外空间吗？如果是这样的话，有没有可能通过不让它递归（而是让它迭代）来用更少的内存来实现呢

private static void quickSort (int[] array, int left, int right) {
    int index = partition(array, left, right);

    //Sort left half
    if (left < index - 1)
        quickSort(array, left, index - 1);

    //Sort right half
    if (index < right)
        quickSort(array, index , right);
}

private static int partition (int array[], int left, int right) {
    int pivot = array[(left + right) / 2]; //Pick pivot point
    while (left <= right) {
        //Find element on left that should be on right
        while (array[left] < pivot)
            left++;

        //Find element on right that should be on left
        while (array[right] > pivot)
            right--;

        //Swap elements and move left and right indices
        if (left <= right) {
            int temp = array[left];
            array[left] = array[right];
            array[right] = temp;
            left++;
            right--;
        }
    }
    return left;
}

Answer 1

子列表的大小在每次连续递归调用时减半，当子列表为1时，递归终止。因此，你对一个元素进行操作的次数等于你在达到1之前将n除以2的次数；日志（n）

Answer 2

如果你进一步阅读维基百科的文章，你会发现一个更thorough discussion of space complexity。他们特别写道：

Quicksort with in-place and unstable partitioning uses only constant additional space before making any recursive call. Quicksort must store a constant amount of information for each nested recursive call. Since the best case makes at most O(log n) nested recursive calls, it uses O(log n) space. However, without Sedgewick's trick to limit the recursive calls, in the worst case quicksort could make O(n) nested recursive calls and need O(n) auxiliary space.

实际上，O（logn）内存什么都不是。例如，如果要对10亿个整数进行排序，存储它们需要4GB，但堆栈只需要大约30个堆栈帧，大约40字节，因此总共大约1200字节