Tag: quicksort

为什么QuickSort使用O（log（n））额外空间？

我已经实现了以下快速排序算法。 在线我已经读过它的空间要求为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[], […]