具有 O(log n) 额外空间(堆栈)的迭代快速排序

Question

你好，我已经用堆栈编写了快速排序，但我不确定这个藻类是否使用了 O(n( 额外的空间或 O(log n( 我想制作的额外空间。

如果有人可以查看此代码并告诉我这里堆栈使用什么额外空间，如果它使用 O(n( 额外空间，我将不胜感激，如何只使用 O(log n( 额外空间？

这是我的代码

public class QuickSortStack{
public static void quickSortStack(int[] tab, int L, int R) {
    Stack<Integer> stack = new Stack();

    while (L < R || !stack.isEmpty()) {
        if (L < R) {
            int q = lomutoPartition(tab, L, R);
            stack.push(R);
            R = q - 1;
        } else {
            L = R + 2;
            R = stack.pop();
        }
    }//end of while
}//end of QS method
public static void main(String[] args) {
    int[] test= {-4,2,-4,2,-12,5,-1,6,-9,0,9}; 
    Random random = new Random();
    int[] tab= new int[20];

    for (int i = 0; i < 20; i++) {
        tab[i] = random.nextInt(50);
        System.out.print(tab[i] + " ");
    }
    System.out.println();
    quickSortStos(tab, 0, tab.length - 1);
    for (int x : tab
            ) {
        System.out.print(x + " ");
    }
}
public static void swap(int[] tab, int i, int j) {
    int tmp = tab[i];
    tab[i] = tab[j];
    tab[j] = tmp;
}
public static int lomutoPartition(int[] tab, int L, int R){
    int i = L-1;
    int x = tab[R]; 

    for(int j = L; j < R; j++){
        if(tab[j] <= x){
            i = i+1;
            swap(tab, i, j);
        }
    }
    swap(tab, i+1, R);
    return i+1;
}

Answer 1

为了保证 O(log N( 空间的使用，您需要推送两个分区中较大的一个，并使用较小的分区进行循环。这相当于递归解决方案，其中非尾递归始终是较小的分区，保证堆栈深度不超过日志₂N。

当你这样做时，你将需要推动分区的两个边界，或者至少一个布尔值来告诉你它是第一个还是第二个分区。

Fwiw，常见的经验是迭代解决方案并不比递归解决方案快。递归实现是安全的，只要你尾部调用优化第二个递归(对于较大的分区(;如果您的语言不能保证总体拥有成本，则很容易手动完成。