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;
}


//cpp/8761