void sort(int input[],int output[], int n) 
{ 
  int m=n; 
  //cout<<m<<endl; 
   
  int i,j,temp; 
  bool exchange;//交换标志 
  for(i=0;i<m-1;i++) 
  { //最多做n-1趟排序 
    exchange=FALSE; //本趟排序开始前，交换标志应为假 
    for(j=m-2;j>=i;j--) //对当前无序区R[i..n]自下向上扫描 
      if(input[j+1]<input[j]) 
      {//交换记录 
        temp=input[j+1]; //R[0]不是哨兵，仅做暂存单元 
        input[j+1]=input[j]; 
        input[j]=temp; 
        exchange=TRUE; //发生了交换，故将交换标志置为真 
      } 
      if(!exchange) //本趟排序未发生交换，提前终止算法 
        break; 
      //cout<<input[5]<<endl; 
  }  
   
  for(int wc1=0; wc1<m; wc1++)//只是来显示排序结果~ 
  { 
    cout<<input[wc1]<<" "; 
  } 
  cout << endl; 
   
  int q=m-1; 
  if((m%2)==0) 
  { 
    int mid=m/2; 
    for (int tempmid=0; tempmid<=mid; tempmid++)//注意循环语句的执行顺序 
    { 
      output[mid+tempmid]=input[q]; 
      q--; 
      output[mid-tempmid-1]=input[q]; 
      q--; 
    } 
  } 
   
  if((m%2)!=0)//注意循环语句的执行顺序 
  { 
    int mid=q/2; 
    output[mid]=input[q]; 
    for (int tempmid=1;tempmid<=mid;tempmid++) 
    { 
      q--; 
      output[mid-tempmid]=input[q]; 
      q--; 
      output[mid+tempmid]=input[q]; 
    } 
  } 
   
  for(int wc=0; wc<m; wc++) 
  { 
    cout<<output[wc]<<" "; 
  } 
  cout << endl; 
} 

int main() 
{ 
   int input[] = {3, 6, 1, 9, 7, 8, 2}; 
   int wc=0; 
   int nCount = sizeof(input)/sizeof(int); 
   for(wc=0; wc<nCount; wc++)// 
  { 
    cout<<input[wc] << " "; 
    //cout<<"\n"<<endl; 
  } 
  cout << endl; 
 
  int output[]= {3, 6, 1, 9, 7, 8, 2}; 
  sort(input,output, nCount); 
   
  return 0; 
}