问题描述：
一个栈中元素类型为整型，现在想将该栈从顶到底按从大到小排序，只许申请一个栈，除此之外可以申请新的变量，但不能申请额外的数据结构，如何完成排序？
原理
其实很简单，建立一个辅助栈，当辅助栈为空的时候直接将数据栈的栈顶压入辅助栈中。
如果不是空，则比较数据栈的栈顶和辅助栈的栈顶，如果小于辅助栈的栈顶，则将数据栈的栈顶压入辅助栈中。如果大于，则将辅助栈大于数据栈栈顶元素压入数据栈中，直到辅助栈为空或者辅助栈的栈顶大于数据栈的栈顶。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| def sort(stack,top):
tmp_stack = [None for k in range(len(stack))]
tmp_top = -1
while(top is not -1):
if tmp_top is -1:
tmp_top += 1
tmp_stack[tmp_top] = stack[top]
top -= 1
else:
last = stack[top]
top -= 1
if last > tmp_stack[tmp_top]:
while(True):
if tmp_top is -1:
break
if last <= tmp_stack[tmp_top]:
break
top += 1
stack[top] = tmp_stack[tmp_top]
tmp_top -= 1
tmp_top += 1
tmp_stack[tmp_top] = last
else:
tmp_top += 1
tmp_stack[tmp_top] = last
print(tmp_stack)
stack = [5,1,3,4,2,1]
top = 5
sort(stack,top)
|
