algorithm - 是否可以使用归并排序对堆栈进行排序？

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

现在，使用它，并假设您也可以使用 size()，它很容易实现，并且是大多数堆栈实现的标准——我们可以实现归并排序:

伪代码:

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

正确性:
Base: stop子句是一个空栈，已排序。
假设:s1和s2已排序。
步骤: 反转后，s1和s2基本上按照lower->higher的顺序遍历，在pop()方法取出元素时在sorted区。由于我们总是从每个堆栈中插入较小的元素，并且我们从低到高遍历每个堆栈 - 我们得到的结果堆栈是有序的。

复杂性:
不包括递归调用，每一步都是O(stack.size()) = O(n)。这与常规合并排序的行为相同，其余的复杂性遵循原始合并排序的相同步骤以获得 O(nlogn)。