假设这里允许的唯一数据结构是堆栈,那么您可以使用2个堆栈。
迭代直到原始堆栈为空,并且在每次迭代中,从原始堆栈中弹出一个元素,而第二个堆栈中的顶部元素大于被删除的元素,弹出第二个堆栈并将其推入原始堆栈。现在,您可以将最初从原始堆栈弹出的元素推送到第二个堆栈。
该方法的时间复杂度为O(N ^ 2)。
实现此算法的C代码将是(请原谅我生锈的C技能):
void SortStack(struct Stack * orig_stack)
{
struct Stack helper_stack;
while (!IsEmpty(orig_stack))
{
int element = Pop(orig_stack);
while (!IsEmpty(&helper_stack) && Top(&helper_stack) < element)
{
Push(orig_stack, Pop(&helper_stack));
}
Push(&helper_stack, element);
}
while (!IsEmpty(&helper_stack))
{
Push(orig_stack, Pop(&helper_stack));
}
}