是否可以使用合併排序對堆棧進行排序？

Question

一個堆棧可以實現爲一個鏈表。 鏈表可以用歸併排序來排序： 爲O（n log n）的時間 O（n）的空間

這是有道理的，以便能夠使用排序合併排序堆。

如果是這樣的話，代碼將是什麼樣子？

（在網絡上快速搜索後，我才發現蠻力算法爲O（n^2））

Answer 1

是的，我們能做到。技巧是理解當棧被排序時，頭是最大的元素 - 我們希望將它從低到高迭代。但是我們可以在O（n）中反轉棧。現在

reverse(stack): 
    s <- new stack 
    while stack.isEmpty() == false: 
     s.push(stack.pop) 
    return s 

，使用它，並假設你可以使用大小（）爲好，這是非常容易實現，對於大多數堆棧實現標準的 - 我們可以實現合併排序：

僞代碼：

mergeSort(stack): 
    if stack.isEmpty(): 
     return stack 
    s1 <- new stack 
    s2 <- new stack 
    // O(n): 
    while s1.size() < stack.size(): 
     s1.push(stack.pop()) 
    while (stack.isEmpty() == false): 
     s2.push(stack.pop())   
    mergeSort(s1) //half the size of stack 
    mergeSort(s2) //half the size of stack 
    //head of s1 and s2 is the largest element 
    s1 <- s1.reverse() //easily implemented in O(n) 
    s2 <- s2.reverse() 
    //now head of s1 and s2 is the smallest element 
    while (s1.isEmpty() == false and s2.isEmpty() == false): 
     if (s1.peek() < s2.peek()): 
      stack.push(s1.pop()) 
     else: 
      stack.push(s2.pop()) 
    //the 'tail' of one stack: 
    while (s1.isEmpty() == false): 
     stack.push(s1.pop()) 
    while (s2.isEmpty() == false): 
     stack.push(s2.pop()) 
    //head is the largest, stacks are sorted 
    return stack 

正確性：
基地：停止子句是一個空棧，其排序。
假設：s1和s2被排序。
步驟：反轉後，當使用pop（）方法取出元素時，s1和s2基本上按照lower-> higher的順序遍歷。由於我們總是從每個堆棧中插入較小的元素，並且我們將每個堆棧從低到高遍歷 - 我們得到的結果堆棧是有序的。

複雜性：
剔除遞歸調用，每一步都是O(stack.size()) = O(n)。這與常規合併排序的行爲相同，其餘複雜性遵循原始合併排序的相同步驟以獲得O(nlogn)。

Answer 2

也許我錯過了這一點，但我會做這種方式：

void mergesortStack(Stack input) { 
    if (input.isEmpty()) { 
     return; 
    } 

    Stack stackLeft = new Stack(); 
    Stack stackRight = new Stack(); 

    // split 
    while (!input.isEmpty()) { 
     stackLeft.push(input.pop()); 
     if (!input.isEmpty()) { 
      stackRight.push(input.pop()); 
     } 
    } 

    // recurse 
    if (!stackLeft.isEmpty() && !stackRight.isEmpty()) { 
     mergesortStack(stackLeft); 
     mergesortStack(stackRight); 
    } 

    // merge 
    Stack tmpStack = new Stack(); 
    while (!stackLeft.isEmpty() || !stackRight.isEmpty()) { 
     if (stackLeft.isEmpty()) { 
      tmpStack.push(stackRight.pop()); 
     } else if (stackRight.isEmpty()) { 
      tmpStack.push(stackLeft.pop()); 
      // set an appropriate compare method 
     } else if (stackLeft.peek().compareTo(stackRight.peek()) >= 0) { 
      tmpStack.push(stackLeft.pop()); 
     } else { 
      tmpStack.push(stackRight.pop()); 
     } 
    } 

    // reverse stack 
    while (!tmpStack.isEmpty()) { 
     input.push(tmpStack.pop()); 
    } 
}