为什么快速排序使用为O（log（n））的额外空间？ [英] Why does QuickSort use O(log(n)) extra space?

问题描述

我已经实现了以下快速排序算法。网上我读它有哦的空间需求（的log（n））。为什么会出现这种情况？我不会创建任何额外的数据结构。

难道是因为我的递归将使用在堆栈上一些额外的空间？如果是这样的话，是有可能通过没有它是递归的（而不是使之成为迭代）？用更少的内存来做到这一点。

 私有静态无效快速排序（INT []数组，诠释左，右诠释）{
    INT指数=分区（阵列，左，右）;

    //排序左前卫
    如果（左＆LT;指数 -  1）
        快速排序（阵，左，指数 -  1）;

    //排序右半
    如果（指数＆LT;右）
        快速排序（数组，指数，权）;
}

私有静态诠释分区（int数组[]，诠释左，右诠释）{
    INT支点=阵列[（左+右）/ 2]。 //选取支点
    而（左＆LT; =右）{
        //查找元素的左边应该是正确的，
        而（数组[左]＆LT;枢）
            离开++;

        //查找元素应该在左边这一权利
        而（数组[右]＆GT;枢）
            对 - ;

        //交换元件和左右移动指数
        如果（左＆LT; =右）{
            INT TEMP =阵列[左]
            阵列[左] =阵列[右]
            阵列[右] =温度;
            离开++;
            对 - ;
        }
    }
    返回左;
}
 

解决方案

正确的，额外的空间是日志（n）的堆栈帧。从快速排序的维基百科的文章：

  

还有一个更复杂的版本，它使用就地分区   算法，并使用O（log n）的空间，可以实现完全排序（不   依靠平均的输入）（用于调用栈）

另外，我觉得这使得它的迭代是不可能的，因为它不是尾递归。

最后，正如其他的答案已经指出，O（日志（N））是pretty的多所有的实际应用非常的非常的小。每一个常数因子，就像你的数据结构的开销，都会对内存使用的影响更大。

I have implemented the below quicksort algorithm. Online I've read that it has a space requirement of O(log(n)). Why is this the case? I'm not creating any extra data structures.

Is it because my recursion will use some extra space on the stack? If this is the case, is it possible to do it with less memory by not having it be recursive (instead making it iterative)?

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

解决方案

Correct, the extra space are the log(n) stack frames. From the Wikipedia article of Quicksort:

There is a more complex version which uses an in-place partition algorithm and can achieve the complete sort using O(log n) space (not counting the input) on average (for the call stack).

Also, I think that making it iterative is not possible because it is not tail recursive.

Finally, as other answers have pointed out, O(log(n)) is for pretty much all practical applications very, very small. Every constant factor, like the overhead of your data structure, will have a greater impact on memory usage.

这篇关于为什么快速排序使用为O（log（n））的额外空间？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！