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） 這幾種情況。