具有 O(log n) 额外 space（堆栈）的迭代快速排序

Question

你好，我已经用堆栈编写了 QuickSort，但我不确定这个算法是否使用了 O(n) extra space 或 O(log n) extra space 我想做的。

如果有人能看一下这段代码并告诉我 extra space 在这里使用什么堆栈，如果它使用 O(n) extra space 如何使用它，我将非常感激只有 O(log n) 额外 space?

这是我的代码

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) space的使用率，您需要推送两个分区中较大的分区并循环使用较小的分区。这相当于一个递归解决方案，其中非尾递归总是较小的分区，保证堆栈深度不超过 log₂N.

执行此操作时，您将需要推动分区的两个边界，或者至少需要一个布尔值来告诉您它是第一个还是第二个分区。

Fwiw，通常的经验是迭代解决方案并不比递归解决方案快。只要您尾调用优化第二个递归（对于较大的分区），递归实现就是安全的；如果您的语言不能保证 TCO，手工操作很容易。

具有 O(log n) 额外 space（堆栈）的迭代快速排序

Iterative QuickSort with O(log n) extra space (stack)

java

algorithm

quicksort