#include?
#include?
#include?
#define??TRUE?1
?
/*
	*?函數(shù)名:?main
	*?功能：實(shí)現(xiàn)快速排序的主程序
	*?輸入：argc為命令行參數(shù)個(gè)數(shù)；
	*???????argv為每個(gè)命令行參數(shù)組成的字符串?dāng)?shù)組。
	*?輸出：返回0代表程序正常結(jié)束
*/
main（int?argcchar?*argv[]）
{
	int?DataSize;
	int?*data;
	/*MyID表示進(jìn)程標(biāo)志符；SumID表示組內(nèi)進(jìn)程數(shù)*/
	int	MyID?SumID;
	int?i?j;
	int?m?r;

	MPI_Status?status;
	/*啟動(dòng)MPI計(jì)算*/
	MPI_Init（&argc&argv）;

	/*MPI_COMM_WORLD是通信子*/
	/*確定自己的進(jìn)程標(biāo)志符MyID*/
	MPI_Comm_rank（MPI_COMM_WORLD&MyID）;	

	/*組內(nèi)進(jìn)程數(shù)是SumID*/
	MPI_Comm_size（MPI_COMM_WORLD&SumID）;	
	
	/*根處理機(jī)（MyID=0）獲取必要信息，并分配各處理機(jī)進(jìn)行工作*/
	if（MyID==0）
	{
		/*獲取待排序數(shù)組的長(zhǎng)度*/
		DataSize=GetDataSize（）;
		data=（int?*）malloc（DataSize*sizeof（int））;

		/*內(nèi)存分配錯(cuò)誤*/
		if（data==0）?
			ErrMsg（“Malloc?memory?error!“）;

		/*動(dòng)態(tài)生成待排序序列*/
		srand（396）;
		for（i=0;i		{
			data[i]=（int）rand（）;
			printf（“%10d“data[i]）;
		}
		printf（“\n“）;
	}

	m=log2（SumID）;

	/*?從根處理器將數(shù)據(jù)序列廣播到其他處理器*/
	/*{“1“表示傳送的輸入緩沖中的元素的個(gè)數(shù)	???*/
	/*?“MPI_INT“表示輸入元素的類型			???*/?
	/*?“0“表示root?processor的ID??}			???*/
	MPI_Bcast（&DataSize1MPI_INT0MPI_COMM_WORLD）;
	
	/*ID號(hào)為0的處理器調(diào)度執(zhí)行排序*/
	para_QuickSort（data0DataSize-1m0MyID）;
????
	/*ID號(hào)為0的處理器打印排序完的有序序列*/
	if（MyID==0）
	{
		for（i=0;i		{
			printf（“%10d“data[i]）;
		}
		printf（“\n“）;
	}

	MPI_Finalize（）;		//結(jié)束計(jì)算
}


/*
	*?函數(shù)名:?para_QuickSort
	*?功能：并行快速排序，對(duì)起止位置為start和end的序列，使用2的m次冪個(gè)處理器進(jìn)行排序
	*?輸入：無序數(shù)組data[1n]，使用的處理器個(gè)數(shù)2^m
	*?輸出：有序數(shù)組data[1n]
*/
para_QuickSort（int?*dataint?startint?endint?mint?idint?MyID）
{
	int?i?j;
	int?r;
	int?MyLength;
	int?*tmp;
	MPI_Status?status;

	MyLength=-1;

	/*如果可供選擇的處理器只有一個(gè)，那么由處理器id調(diào)用串行排序，對(duì)應(yīng)于算法13.4步驟（1.1）*/
	/*（1.1）	Pid?call?quicksort（dataij）?*/
	if（m==0）
	{
		if（MyID==id）
			QuickSort（datastartend）;
		return;
	}	

	/*由第id號(hào)處理器劃分?jǐn)?shù)據(jù)，并將后一部分?jǐn)?shù)據(jù)發(fā)送到處理器id+exp2（m-1），對(duì)應(yīng)于算法13.4步驟（1.21.3）*/
	/*（1.2）?Pid:?r=patrition（dataij）*/	
	if（MyID==id）
	{
		/*將當(dāng)前的無序區(qū)R[1，n]劃分成左右兩個(gè)無序的子區(qū)R[1，i-1]和R[i，n]（1≤i≤n）*/
		r=Partition（datastartend）;	
		MyLength=end-r;	
		/*（1.3）	Pid?send?data[r+1m-1]?to?P（id+2m-1）?*/
		/*?{MyLength表示發(fā)送緩沖區(qū)地址；*/
		/*??發(fā)送元素?cái)?shù)目為1;		???*/
		/*??MyID是消息標(biāo)簽?}		???*/
		MPI_Send（&MyLength1MPI_INTid+exp2（m-1）MyIDMPI_COMM_WORLD）;
		/*若緩沖區(qū)不空，則第id+2m-1號(hào)處理器取數(shù)據(jù)的首址是data[r+1]*/
		if（MyLength!=0）
			MPI_Send（data+r+1MyLengthMPI_INTid+exp2（m-1）MyIDMPI_COMM_WORLD）;
	}

	/*處理器id+exp2（m-1）接受處理器id發(fā)送的消息*/
	if（MyID==id+exp2（m-1））
	{
		MPI_Recv（&MyLength1MPI_INTididMPI_COMM_WORLD&status）;
		if（MyLength!=0）