华为OJ—火车进站（栈，字典排序）

ybaidukuai

　　给定一个正整数N代表火车数量，0<N<10，接下来输入火车入站的序列，一共N辆火车，每辆火车以数字1-9编号。要求以字典序排序输出火车出站的序列号。其实也就是输出所有可能的出栈序列。
　　样例输入：
　　3
　　1 2 3
　　样例输出：
　　1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
　　解答：
　　其实核心就是一个栈，对于第K个数，在第K个数进栈之前，前面的 K-1 个数要么全部出去了，要么都在栈里面，要么部分在栈里面部分出去了。那么可以假想，在第K个数入栈之前，依次从栈里面出去 0个、1个、2个……栈.size()个，然后把第K个入栈，再对于 K+1个同样实施这样的方法——这就是个递归了。
　　出去了的保存在一个队列里面，没出站的保存在栈里面，最后一辆车处理完了递归结束并输出。



#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int n;
int *pArr=NULL;
void handle(int index, stack<int> s, vector<int> v,vector<vector<int> >& res)
{
//对于每一个待处理的数字，先处理栈里面的，再处理这个数字
for (int i = s.size(); i >=0; i--)
{
//栈里面的数字可以出来 [0个, 全部]，出来的就放到了vector里面待输出了
stack<int> sTemp(s);
vector<int>vTemp(v);
//从栈里面出 i 个到队列里面去
for (int j = 1; j <= i; j++)
{
int top = sTemp.top();
sTemp.pop();
vTemp.push_back(top);
}
//再处理这个，把它放到栈顶
         
sTemp.push(pArr[index]);
if (n-1==index)
{
//输出结果
vector<int> vRes;
for (int i = 0; i < vTemp.size(); i++)
vRes.push_back(vTemp);
while (!sTemp.empty())
{
int top = sTemp.top();
sTemp.pop();
vRes.push_back(top);
}     
res.push_back(vRes);
}
else
{
//递归处理
handle(index+1, sTemp, vTemp,res);
}
}
}

void swap(vector<vector<int> >& d,int low,int high)
{
int tmp;
for(int i=0;i<d[low].size();i++)
{
tmp=d[low];
d[low]=d[high];
d[high]=tmp;
}
}
int compare(vector<int> a1,vector<int>a2)
{
int size=a1.size();
for(int i=0;i<size;)
{
if(a1==a2)
i++;
else
{
if(a1>a2)
return 1;
else
return -1;
}
}
}

void fast_sort(vector<vector<int> >& d,int low,int high)
{
int left=low,right=high;
if(low>=high)
return;
while(left!=right)
{
if(compare(d[right],d[low])>0 &&left<right)
right--;
if(compare(d[left],d[low])<0 && left<right)
left++;
if(left<right)   
swap(d,left,right);   
}
swap(d,low,left);
fast_sort(d,low,left-1);
fast_sort(d,left+1,high);
}

void dictionary_sort(vector<vector<int> >& d)
{
if(d.size()<2)
return;
else
{
int tmp;
for(int i=0;i<d.size();i++)
{
flag=d.size();
tmp=0;
for(int j=0;j<flag;j++)
{
coeff=1;
for(int k=1;k<flag-j;k++)
coeff*=10;
tmp+=d[j]*coeff;
}        
v_tmp.push_back(tmp);
}
fast_sort(d,0,v_tmp.size()-1);
return;
}

}
int main(void)
{
cin >> n;
pArr=new int[n];
vector<vector<int> > result;
for (int i = 0; i < n; i++)
cin >> pArr;
stack<int> s;
vector<int> v;
handle(0, s, v,result);   
dictionary_sort(result);
for(int i=0;i<result.size();i++)
{
for(int j=0;j<n-1;j++)
cout<<result[j]<<" ";
cout <<result[n-1]<<endl;
}
delete [] pArr;
}

函数 void dictionary_sort()是对得到的结果按字典序排序。字典序排序的具体方法为快速排序法，由于数据比较小，也可用冒泡排序法。
　　参考：  华为OJ—火车进站（栈，字典排序）