是否可以使用合并排序对堆栈进行排序？

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()); 
    } 
}