3-09. 队列中的元素排序【pat】

3-09. 队列中的元素排序

时间限制 50 ms

内存限制 32000 kB

代码长度限制 8000 B

判题程序 Standard

给定一个队列，请用一系列合法的队列操作函数，包括：

（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） 这几种情况。