//                     Stack Sort program in C++//----------------------用栈的方式实现排序----------------//作者：andyhou//题目：//    输入一个栈（不是数组），并且程序中只允许使用一定的整数及栈。//    结束时排序结果放在栈中，栈顶的元素最小。//算法复杂度：//     在最差情况下。算法的执行时间是@（N~2);#include <iostream>#include <stack>using namespace std; //输入栈的函数。void EnStack(stack<int> &Astack,int n){ int item; cout<<"Enter the  the data element: "; for(int i=0;i<n;i++) {  cin>>item;  Astack.push(item); }}//采用两个栈的方式实现栈的转换后排序。void StackSort(stack<int> &Astack,int n){ using std::stack; stack<int> Bstack;  //申请一个临时的栈用来转换。 for(int i=0;i<n;i++) {  for(int j=i;j<n-1;j++)//注意临界的情况。  {       int temp1=Astack.top();       Astack.pop();    int temp2=Astack.top();    Astack.pop();       if(temp1<temp2)     //弹出两个元素。小的到临时栈中。    {                   //大的照样压回栈中。         Bstack.push(temp1);         Astack.push(temp2);    }    else    {     Bstack.push(temp2);     Astack.push(temp1);    }  }  for(int k=i;k<n-1;k++)//再把临时栈中的元素回放到原栈中。  {                     //此时原栈的栈底是最大的元素。   Astack.push(Bstack.top());   Bstack.pop();  } }  //反复的找到最大的元素放到栈底。 } void print(stack<int> Astack,int n){ cout<<"print all number after sort!"<<endl; for(int i=0;i<n;i++) {  cout<<Astack.top()<<"  ";  Astack.pop(); } cout<<endl;} int main(){ int n;    using std::stack;    stack<int> Astack; cout<<"Enter the sum of the data element: "<<endl; cin>>n; EnStack(Astack,n); StackSort(Astack,n); print(Astack,n); return 0;}//此题思路就是冒泡排序的思想。排序比较耗时。不实用！     

评论