给定一个队列，请用一系列合法的队列操作函数，包括：
（1） int IsEmptyQ(Queue Q)
（2） void AddQ(Queue Q, ElementType item)
（3） ElementType DeleteQ(Queue Q)
将队列中的元素从小到大排序。
注意：不能直接通过数组下标直接访问队列（数组）中的元素。可以使用一个辅助队列。排序后的结果应存放在原队列中。
输入格式说明：
输入首先给出1个正整数N(<=105)，表示队列中元素的个数。随后按入队的顺序给出N个整数（这里假设item为整型数字）。
输出格式说明：
在一行中输出排序后出队的序列。数字间以空格分隔，但末尾不得有多余空格。
样例输入与输出：
| 序号 | 输入 | 输出 |
| 1 |
10 9 4 6 1 8 3 7 0 2 5 |
0 1 2 3 4 5 6 7 8 9 |
【结题报告】：这个题目还是蛮有意思的，乍一看以为是普通的排序题。仔细看条件：只能用两个队列以及其合法操作，不能访问下标。出题人的意图应该是考你模拟排序算法的过程。排序算法就那么几种。复杂度O(N^2)的肯定不行，题设时间只有50ms。剩下的可能是归并排序或者是快速排序。条件限制不能访问下标，辅助空间也只有一个队列，quick sort应该不行。那就往merge sort的方向去想，merge的思路很简单先分成小组，组内合并排序然后组间合并排序。按理来说我们需要三个队列，两个合并后放到第三个里面。但是题目本身只有两个队列，那么结果放哪里呢。答案就是：原始队列的尾部！想到到这里思路就清楚了。
#include<iostream>
#include<queue>
#include<math.h>
#include<time.h>
using namespace std;
deque<int> que1;
deque<int> que2;
void print_q(deque<int> que)
{
bool first=true;
while(!que.empty())
{
if(!first)
printf(" %d",que.front());
else
printf("%d",que.front());
first=false;
que.pop_front();
}
}
void merge_sort(int n,int m,deque<int>& que,deque<int>& que2)
{
int i=0,j=0;
i=0;
j=0;
while(i<m&&j<n)
{
if(que.front()<que2.front())
{
que.push_back(que.front());
que.pop_front();
i++;
}
else
{
que.push_back(que2.front());
que2.pop_front();
j++;
}
}
while(i<m)
{
que.push_back(que.front());
que.pop_front();
i++;
}
while(j<n)
{
que.push_back(que2.front());
que2.pop_front();
j++;
}
}
void que_pop(int num,deque<int>&que_out,deque<int>& que_in)
{
int i=0;
for(i=0;i<num;i++)
{
que_in.push_front(que_out.back());
que_out.pop_back();
}
}
void merge_div(int n,int m, deque<int>& que,deque<int>& que2)
{
int i=0;
if(n!=1)
merge_div(n/2,n-n/2,que,que2);
if(m!=1)
merge_div(m/2,m-m/2,que,que2);
if((n==1&&m==1))
{
que2.push_back(que.front());
que.pop_front();
merge_sort(n,m,que,que2);
}
else//if m n doesn‘t equal 1 they should be combine with other nums
{
if(n==1)
{
que_pop(m,que,que2);
merge_sort(m,n,que,que2);
}
else if(m==1)
{
que_pop(n,que,que2);
merge_sort(n,m,que,que2);
}
else
{
que_pop(m,que,que2);
que_pop(n,que,que);
merge_sort(m,n,que,que2);
}
}
}
int main()
{
int n=0,i=0;
int temp=0;
while(scanf("%d",&n)!=EOF)
{
////////
// n=100;
//int time_s=time(NULL);
for(i=0;i<n;i++)
{
scanf("%d",&temp);
//temp=rand();
que1.push_front(temp);
}
merge_div(n/2,n-n/2,que1,que2);
print_q(que1);
//int time_e=time(NULL);
//printf("\n%d---%d",time_e,time_s);
}
return 0;
}
调试的时候要注意 （1 1） （1 m） （n 1） 这几种情况。
3-09. 队列中的元素排序【pat】,布布扣,bubuko.com
原文：http://blog.csdn.net/linsheng9731/article/details/22980839