排序堆栈的算法

哪种排序算法可以很好地对堆栈进行排序以获得空间效率？我需要对堆叠进行排序。“我对“就地”算法的理解是，他们不使用任何额外的数据结构 - 这是正确的吗？排序堆栈的算法

我知道这是类似于this question但我不知道它是否会成为堆栈不同？我知道堆栈可以只是一种链接列表，但是你只能访问顶部的事实会改变你如何做到这一点？

2016-07-16 user146303

做无[结果]（https://www.google.com/search#q=sort+stack+in+place）回答你的问题吗？ – dimo414

如果您仅限于使用堆栈的功能，比如push和pop，那么您肯定需要一些空间来对其进行排序。但如果允许您触摸堆栈实现，我们可以高效地完成这个空间。（如果堆栈是使用链表创建的，那么我们可以使用链表的功能进行排序） – pahan

顺便说一句，当您对堆栈进行排序时，它将不再是堆栈。因此，如果您处于需要对堆栈进行排序的情况，您肯定会需要另一个数据结构来存储排序后的值以保留堆栈。 – pahan

你将不得不省略“就地”预选赛，如果你的目的是要排序只使用堆栈操作堆栈（你必须有另一个堆栈）。原地算法是一种不使用其他数据结构来转换其输入的算法。但是，中间/临时变量允许少量额外的存储空间。

如果省略了“就地”限定词，你可以在这里找到答案：How to sort a stack using only stack operations?（排序使用额外的助手堆栈，堆栈）

如果保留预选赛然后排序堆是唯一可能的实现级别，而不是使用堆栈操作。

2016-07-16 20:42:03

有一个替代定义为就地那种只是意味着已排序的数据结束备份在同一容器（在这种情况下的堆叠）该未排序的数据最初被存储英寸

再回到原始问题，访问和/或更改堆栈最后一个元素的唯一方法是从所有其他元素中弹出，这需要在其他地方存在O（n-1）个空间，最简单的是一个数组。

如果堆栈作为一个链表实现，那么一个链表排序类型可以使用，但是这将是面向列表排序，使用超过标准的堆栈操作之外偷看，POP和推动。

2016-07-17 09:52:36 rcgldr

回答