堆栈可以实现为链表。可以使用合并排序对链接列表进行排序：O（n log n）时间O（n）空间
能够使用合并排序对堆栈进行排序很有意义。
如果是这样，代码将是什么样？
（在网上快速搜索之后，我只发现了暴力算法O（n ^ 2））
我们可以。诀窍在于理解，当对堆栈进行排序时，head是最大的元素-我们希望将其从低到高进行迭代。但是，可以在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
正确性：
基础：stop子句是一个空堆栈，已排序。
假设：对s1和s2进行排序。
步骤：反转后，使用pop（）方法取下元素时，在排序区域中，s1和s2基本按照从低到高的顺序遍历。由于我们总是从每个堆栈中插入较小的元素，并且我们从低到高遍历每个堆栈-我们得到的结果堆栈是有序的。
复杂度：
除递归调用外，每个步骤均为O(stack.size()) = O(n)。这与常规合并排序的行为相同，其余复杂性遵循原始合并排序要获取的相同步骤O(nlogn)。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句