/*?Copyright（c）?2009?LuoMin?CSU?P.R.China
?*?All?right?reserved
?*
?*?Abstract:
?*
?*/
#include?“mpi.h“
#include?
#include?
#include?

/////////////冒泡排序/////////////

void?Sort（int?*a?int?len）
{
	int?i;
	bool?change;
	int?temp;

	for（i=len-1?change=true;?i>=1;?--i）
	{
		change?=?false;
		
		for（int?j=0;?j		{
			if（a[j]?>?a[j+1]）
			{
				temp?=?a[j];
				a[j]?=?a[j+1];
				a[j+1]?=?temp;
				change?=?true;
			}
		}
	}
}

int?main（int?argc?char?**argv）
{
	
	int?Size;
	int?MyId;
	MPI_Status?status;
	int?n?;

	int?l;

	int?*Number;?//保存全局數據的緩沖區
	int?*Local;??//保存分配到得數據
	int?*Sample;?//選擇樣本
	int?*AllSample;?//?所有的樣本
	
	
	
	
	double?startTime?endTime;?//記錄程序運行的墻上時間

	MPI_Init（&argc?&argv）;
	MPI_Comm_size（MPI_COMM_WORLD?&Size）;
	MPI_Comm_rank（MPI_COMM_WORLD?&MyId）;

	
	if?（?MyId?==0）
	{
		fprintf（stdout?“Please?input?number?of?elements?to?be?sorted\n“）;
		fflush（stdout）;
		
		if?（?Size?==1）
		{
			fprintf（stdout?“The?number?must?be?integer?times?of?%d\n“?Size*Size）;
			fflush（stdout）;
			scanf（“%d“?&n）;
			fflush（stdin）;
		}
		else
		{
			n?=?Size*Size-1;
		

			while（?n%（Size*Size））
			{
				fprintf（stdout?“The?number?must?be?integer?times?of?%d\n“?Size*Size）;
				fflush（stdout）;
				scanf（“%d“?&n）;
				fflush（stdin）;
			}
		}
		
		
		
		l?=?n/Size;?//?待處理的數據數目

		startTime?=?MPI_Wtime（）;
	}

	MPI_Bcast（&l1MPI_INT?0?MPI_COMM_WORLD）;
	
	MPI_Barrier（MPI_COMM_WORLD）;

	if（MyId==0）
	{
		//fprintf（stdout“Please?input?%d?integer?numbers\n“?n）;
		
		//fflush（stdout）;
		
		Number?=?new?int[n];

		srand（time（NULL））;
		for?（?int?i=0;?i		{
			Number[i]?=?rand（）%100;
		}
		fflush（stdin）;

		Local?=?new?int[l];
		for?（?int?k=0;?k		{
			Local[k]?=?Number[k];?//根進程自己分派的數據
			
		}		
		////?//均勻劃分///////
		for?（??int?j=1;?j		{
			MPI_Send（Number+j*l?l?MPI_INT?j?j?MPI_COMM_WORLD）;//向其他進程發送待排序數據
		}
		////////////////////////
	}
	else
	{		
			Local?=?new?int[l];
			MPI_Recv（Local?l?MPI_INT?0?MyId?MPI_COMM_WORLD?&status）;		
		
	}

	MPI_Barrier（MPI_COMM_WORLD）;


	/////局部排序//////
	Sort（Local?l）;
	//////////////////
	

	///////選擇樣本選擇0進程進行樣本排序//////
	Sample?=?new?int[Size];?

	int?w?=?l/Size;

	for（int?i=0;?i	{

		Sample[i]?=?Local[i*w];
	}
	
	if?（MyId?==?0）
	{
		AllSample?=?new?int[Size*Size];
	}
	
	//MPI_Barrier（MPI_COMM_WORLD）;

	MPI_Gather（Sample?Size?MPI_INT?AllSampleSize?MPI_INT?0?MPI_COMM_WORLD）;
	
	MPI_Barrier（MPI_COMM_WORLD）;

	if（MyId?==?0）
	{
		Sort（AllSample?Size*Size）;
		/*fprintf（stdout?“All?sample:?“）;
		for（?int?i=0;?i		{
		
			fprintf（stdout?“%d?“?AllSample[i]）;
		
			fflush（stdout）;
		}*/
		
	//////////選擇主元///////////
	

		delete?[]Sample;		

		Sample?=?new?int[Size-1];
		
		
		for（?int?k=0;?k		{
			Sample[k]?=?AllSample[（k+