按升序对栈进行排序

按升序对栈进行排序（即最大元素位于栈顶）。最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构（如数组）。java

该栈支持以下操做：push， pop， peek，和isEmpty算法

若是能够支持两个栈，咱们能够每一次遍历栈1，将最小的元素放入栈2，把栈3做为搜索时的缓冲区数组

一、方法一：实现初步的排序算法:搜索整个栈，找出最小元素，以后将其压入另外一个栈。而后，在剩余元素中找出最小的压入栈。数据结构

注意：实际上须要三个栈：s1为原栈，s2位最终排好序的栈，s3在搜索s1时用做缓冲区。在s1中搜索最小值，须要弹出s1的元素，并将它们压入缓冲区s3。但最多只能使用一个额外的栈，此方法不合适。app

二、方法二：spa

/** 
 * 从s1中逐一弹出元素，按顺序插入s2中。
 */

咱们不须要反复搜索栈1来依次得到最小值，假设栈s是要排序的栈，栈r是已排序的栈.net

s = [5,10,7]blog

r = [12,8 ,3,1]排序

栈顶元素5在r中的正确位置应该是3的上面，咱们能够先弹出5，反正5是不管如何都要从s压入r的，而后将12和8压入栈s，而后将5压入栈r递归

注意这是12和8没有在r中了，可是只要咱们不改变它们在s中的顺序，重复上面的步骤，12和8一次从s弹出再压入r仍是在5的上面，r依然是有序的。

时间复杂度为O（n^2）,空间复杂度O（n）

[java] view plain copy

1. import java.util.Stack;  
2.   
3.   
4. public class sort {  
5.     public static Stack<Integer> sortStk(Stack<Integer> s) {  
6.         Stack<Integer> r = new Stack<Integer>();  
7.         while( !s.isEmpty() ) {  
8.             int temp = s.pop();  
9.             while ( !r.isEmpty() && r.peek() > temp) {  
10.                 s.push(r.pop());  
11.             }  
12.             r.push(temp);  
13.         }  
14.         return r;  
15.     }  
16. } 

方法三：

前提：若容许使用的栈数量不限。实现修改版的快速排序和归并排序，要求每层递归都建立两个额外的栈。

 *归并排序：建立两个栈，并将原栈分为两部分。递归排序每一个栈，而后将其归并到一块儿并排好序，放回原来的栈中。

 *快速排序：建立两个额外的 栈，并根据基准元素（pivot element）将这个栈分为两个栈，这两个栈会进行递归排序，而后归并在一块儿，放回原来的栈中。