迭代快速排序與O（日誌n）額外的空間（堆棧）

Question

你好，我已經寫入QuickSort與堆棧，但我不知道這alghoritm使用O（n）額外的空間或O（日誌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（日誌N）的空間使用情況，您需要按兩個分區和環的較大與較小的一個。這相當於遞歸解決方案，其中非尾遞歸總是較小的分區，保證堆棧深度不超過log _N

當你這樣做時，你需要推動分區，或至少一個布爾值，告訴你它是第一個還是第二個分區。

Fwiw，常見的經驗是迭代解決方案不會比遞歸解決方案更快。只要您通過tail-call優化第二次遞歸（對於較大的分區），遞歸實現是安全的;如果你的語言不能保證TCO，那麼很容易手工完成。