unstablemerge.cpp

一种快速二路归并算法

			long jj=j+lenoffirstblockofsecondsublist-1;
			long posoffirstblockoffirstsublist=i;//posofnewheadoffirstsublist=ii+1;
			long posoffirstblockofsecondsublist=j;//posofnewheadofsecondsublist=jj+1;
			long head=-1;
//cout<<"分块并排序，记住两个子表的首块的位置和长度"<<endl;
////				count_com++;
			if(*(punsigned+ii)<=*(punsigned+jj)) //第一子序列的首块较小
			{
				i=ii+1,ii=i+sqrtn-1;//跳过子序列1的首块
				while(ii<=divid && *(punsigned+ii)<=*(punsigned+jj))//处理小于子序列2首块的所有块
				{
////					count_com++;
					if(ii==divid)
						goto datasort;//子序列1的所有块都小于子序列2首块，转数据排序
					i=ii+1;ii=i+sqrtn-1;
				}
////					count_com++;
				if(*(punsigned+divid)>*(punsigned+jj))//第一子序列有大于第二子序列的元素，将第2子序列的首块元素前移
				{
					if(jj==endpos)//第2子序列只有首块1个块
					{
						adjacentblockexchange(punsigned,i,divid,endpos);
						posoffirstblockofsecondsublist=i;
						goto datasort;
					}
					adjacentblockexchange(punsigned,i,divid,jj);
					posoffirstblockofsecondsublist=i;
					divid=jj;
					j=jj+1;jj=j+sqrtn-1;
					i+=lenoffirstblockofsecondsublist;
					ii+=lenoffirstblockofsecondsublist;

				}
			}
			else //第二子序列的首块较小
			{
				j=jj+1;jj=j+sqrtn-1;//跳过子序列2的首块
				while(jj<=endpos && *(punsigned+jj)<=*(punsigned+ii))
				{
////					count_com++;
					j=jj+1;jj=j+sqrtn-1;
				}
//					count_com++;
                if(*(punsigned+endpos)>*(punsigned+ii))//第二子序列有大于第一子序列的元素
				{
					adjacentblockexchange(punsigned,i,divid,j-1);
					posoffirstblockofsecondsublist=i;
					i+=j-1-divid;//子序列2前移j-1-divid个元素
					divid=j-1;
					ii=i+lenoffirstblockoffirstsublist-1;
					posoffirstblockoffirstsublist=i;
					if(ii==divid)
						goto datasort;//子序列1只有首块1个块，转数据排序
					i=ii+1;ii=i+sqrtn-1;//跳过子序列1的首块
				}
				else//第二子序列元素全小
				{
					adjacentblockexchange(punsigned,i,divid,endpos);
					posoffirstblockofsecondsublist=i;
					i+=endpos-divid;
					posoffirstblockoffirstsublist=i;//不再进行块排序
					goto datasort;
				}
			}
//cout<<" 处理首块后："<<endl;
			while(ii<=divid && jj<=endpos)
			{
				if(head==-1)//第一子序列中未归并部分有序
				{
//cout<<"第一子序列中未归并部分有序 ："<<endl;
					while(ii<=divid && *(punsigned+ii)<=*(punsigned+jj))//子序列1中块小，不移动
					{i=ii+1,ii+=sqrtn;}//count_com++;
					if(ii<=divid)//子序列2的当前块小，交换并置第一子序列中未归并部分无序标志（正数）
					{
						if(ii==divid)
						{
							do
							{
////								count_com++;
								j=jj+1,jj=j+sqrtn-1;
							}while(jj<=endpos && *(punsigned+jj)<=*(punsigned+ii));
							if(jj<=endpos)
								adjacentblockexchange(punsigned,i,ii,j-1);
							else
								adjacentblockexchange(punsigned,i,ii,endpos);
							goto datasort;//子序列1的尾块处理，块排序结束，转数据排序
						}						
						else
							equalsizeblockexchange(punsigned,i,j,sqrtn);

						head=j;divid+=sqrtn;

						i=ii+1,ii=i+sqrtn-1;
						j=jj+1,jj=j+sqrtn-1;
					}
				}
				else  //第一子序列中未归并部分无序，小的在尾部
				{
//cout<<"第一子序列中未归并部分无序 ："<<endl;
					long findpos=head;
					long f=head+sqrtn,ff=f+sqrtn-1;
					while(ff<=divid )
					{
////						count_com++;
						if(*(punsigned+ff)<*(punsigned+findpos+sqrtn-1))
							findpos=f;
						else if(*(punsigned+ff)==*(punsigned+findpos+sqrtn-1))
						{
//							count_com+=2;
							if(*(punsigned+f)<*(punsigned+findpos))
								findpos=f;
						}
////						else count_com++;
						f=ff+1,ff+=sqrtn;
					}
////						count_com++;
					if(*(punsigned+findpos+sqrtn-1)<=*(punsigned+jj))//子序列1的当前块小，子序列1内部交换
					{
//cout<<"子序列1的当前块小，子序列1内部交换"<<endl;
						if(i!=findpos)//ii>=divid时，子序列1中只剩下最大块，且小于子序列2中未排序块,不交换
							equalsizeblockexchange(punsigned,i,findpos,sqrtn);
						if(ii==divid)
							goto datasort;
						i=ii+1,ii+=sqrtn;
						if(head<i)
							head=i;
					}
					else  
					{   //子序列2的当前块小，交换
//cout<<"子序列2的当前块小"<<endl;
						if(ii==divid)
						{
//cout<<"ii==divid"<<endl;
							do
							{
//								count_com++;
								j=jj+1,jj=j+sqrtn-1;
							}while(jj<=endpos && *(punsigned+jj)<=*(punsigned+ii));
							if(jj<=endpos)
							{
//cout<<"jj<=endpos,len1="<<(divid-i+1)<<",len2="<<(j-1-divid)<<endl;
								adjacentblockexchange(punsigned,i,divid,j-1);
							}
							else
							{
//cout<<"jj>endpos,len1="<<(divid-i+1)<<",len2="<<(endpos-divid)<<endl;
								adjacentblockexchange(punsigned,i,divid,endpos);
							}
							goto datasort;//子序列1的尾块处理，块排序结束
						}						
						else
						{
//cout<<"ii!=divid"<<endl;
							equalsizeblockexchange(punsigned,i,j,sqrtn);
						}
//cout<<"ii!=divid,ok"<<endl;
						i=ii+1,ii+=sqrtn;
						if(head<i)
							head=i;
						divid+=sqrtn;
						j=jj+1,jj=j+sqrtn-1;
					}
				}
			}
//cout<<"处理块1尾："<<endl;
		if(head>-1)
			while(ii<=divid)//子序列2处理完，但子序列1未完，子序列1内部交换
			{
				long f=head+sqrtn,ff=f+sqrtn-1;
				long findpos=head;
				while(ff<=endpos )
				{
////					count_com++;
					if(*(punsigned+ff)<*(punsigned+findpos+sqrtn-1))
						findpos=f;
					else if(*(punsigned+ff)==*(punsigned+findpos+sqrtn-1))
					{
//						count_com+=2;
						if(*(punsigned+f)<*(punsigned+findpos))
							findpos=f;
					}
//					else
//						count_com++;
					f=ff+1,ff=f+sqrtn-1;
				}
				if(i!=findpos)//最后的块不用交换
					equalsizeblockexchange(punsigned,i,findpos,sqrtn);
				i=ii+1,ii=i+sqrtn-1;
				if(head<i)
					head=i;
			}
datasort:
//cout<<"块排序完，数据排序:"<<endl;
			long cur=firstpos;
			i=cur;
			bool findsecondpart=false;
			if(firstpos==posoffirstblockoffirstsublist)//子序列1的首块小
			{
				ii=i+lenoffirstblockoffirstsublist-1;
				j=ii+1;
				do
				{
					findsecondpart=false;
					do//确定第一、第二部分
					{
						if(j==posoffirstblockofsecondsublist)
							jj=j+lenoffirstblockofsecondsublist-1;
						else
							jj=j+sqrtn-1;
						if( *(punsigned+ii)<=*(punsigned+j))//没有找到第二部分
						{
							i=j,ii=jj;
							j=ii+1;
						}
						else
							findsecondpart=true;

					}while(!findsecondpart && j<=endpos  );//确定第一、第二部分
					if(findsecondpart)	//将第一部分全部和第二部分的部分归并
					{
						while(cur<=ii)
						{
							cur=binarysearchgreat(punsigned,cur,ii,j);//确定部分1中插入位置
							if(cur<=ii)
							{
								j++;
								j=binarysearchle(punsigned,j,jj,cur);//确定部分2中前移元素
//if(j-1<=ii) cout<<"error!"<<endl;
								adjacentblockexchange(punsigned,cur,ii,j-1);
								cur+=j-1-ii;//
								ii=j-1;
							}
							else//部分1元素都不大于部分2当前元素
								break;
						}
					}
					if(findsecondpart)//重新确定第1、第2部分
					{
						cur=j,i=j,ii=jj;
						j=ii+1;
					}
				}while(j<=endpos);
			}
			else//子序列2的首块小
			{
				ii=i+lenoffirstblockofsecondsublist-1;
				j=ii+1;
				do
				{
					findsecondpart=false;
					do//确定第一、第二部分
					{
						if(j==posoffirstblockoffirstsublist)
							jj=j+lenoffirstblockoffirstsublist-1;
						else
							jj=j+sqrtn-1;
						if( *(punsigned+ii)<=*(punsigned+j))//没有找到第二部分
						{
							i=j,ii=jj;
							j=ii+1;
						}
						else
							findsecondpart=true;

					}while(!findsecondpart && j<=endpos  );//确定第一、第二部分
					if(findsecondpart)	//将第一部分全部和第二部分的部分归并
					{
						while(cur<=ii)
						{
							cur=binarysearchgreat(punsigned,cur,ii,j);//确定部分1中插入位置
							if(cur<=ii)
							{
								j++;
								j=binarysearchle(punsigned,j,jj,cur);//确定部分2中前移元素
//if(j-1<=ii) cout<<"2:error!"<<endl;
								adjacentblockexchange(punsigned,cur,ii,j-1);
								cur+=j-1-ii;//
								ii=j-1;
							}
							else//部分1元素都不大于部分2当前元素
								break;
						}
					}
					if(findsecondpart)//重新确定第1、第2部分
					{
						cur=j,i=j,ii=jj;
						j=ii+1;
					}
				}while(j<=endpos);
			}
        }
    }
}


void mergesort(eletype *punsigned,long first,long last)
{
	if(first<last)
	{
		if(first<(first+last)/2)
			mergesort(punsigned,first,(first+last)/2);
		if((first+last)/2+1<last)
			mergesort(punsigned,(first+last)/2+1,last);
		merge(punsigned,first,(first+last)/2,last);
	}
}

void advancedmergesort(eletype *punsigned,long first,long last)
{//长度为1的序列本身是有序的
	if(first<last)
	{
		if(first<(first+last)/2)
			advancedmergesort(punsigned,first,(first+last)/2);
		if((first+last)/2+1<last)
			advancedmergesort(punsigned,(first+last)/2+1,last);
		advancedmerge(punsigned,first,(first+last)/2,last);
	}
}

long trantoms(SYSTEMTIME t1,SYSTEMTIME t2)
{
	long temp1,temp2;
	temp1=((t1.wHour*60+t1.wMinute)*60+t1.wSecond)*1000+t1.wMilliseconds;
	temp2=((t2.wHour*60+t2.wMinute)*60+t2.wSecond)*1000+t2.wMilliseconds;
	return (temp2-temp1);
}


void main()
{
	SYSTEMTIME t1,t2;
	long m,n;
	time_t timer1,timer2,timer3,timer4;;//
	eletype *punsigneda,*punsignedb;//
	cout<<"请输入第1子序列元素的个数：";
	cin>>m;
	cout<<"请输入第2子序列元素的个数：";
	cin>>n;
	punsigneda=new eletype[m+n];
	punsignedb=new eletype[m+n];//
	input(punsigneda,m+n);
//	copyunsigneda(punsigneda,punsignedb,m+n);
//	output(punsigneda+80250,96);
//	output(punsigneda,n);
	advancedmergesort(punsigneda,0,m-1);
	advancedmergesort(punsigneda,m,m+n-1);
	copyunsigneda(punsigneda,punsignedb,m+n);//
//	count_com=count_mov=0;
	time(&timer1);
	GetSystemTime(&t1);
    advancedmerge(punsigneda,0,m-1,m+n-1);
//    advancedmergesort(punsigneda,0,m+n-1);
	GetSystemTime(&t2);
	time(&timer2);
	cout<<endl<<"改进排序时长为："<<trantoms(t1,t2)<<"毫秒。"<<endl;
//	cout<<endl<<"改进排序比较次数为："<<count_com<<endl;
//	cout<<endl<<"改进排序移动次数为："<<count_mov<<endl;
//	output(punsigneda+9000,1000);
	right_stable(punsigneda,m+n);
//	output(punsigneda,m+n);
	delete []punsigneda;
//	cin>>n;
	time(&timer3);
//	count_com=count_mov=0;
//    merge(punsignedb,0,m-1,m+n-1);
//    quicksort(punsignedb,0,m-1,m+n-1);
//	mergesort(punsignedb,0,n-1);
//	heapsort(punsignedb,m+n);
	time(&timer4);
//	output(punsignedb,n);
	cout<<endl<<"未改进排序时长为："<<(timer4-timer3)<<"秒。"<<endl;
//	cout<<endl<<"未改进排序比较次数为："<<count_com<<endl;
//	cout<<endl<<"未改进排序移动次数为："<<count_mov<<endl;
//	cout<<endl<<"快速排序时长为："<<(timer4-timer3)<<"秒。"<<endl;
//	cout<<endl<<"堆排序时长为："<<(timer4-timer3)<<"秒。"<<endl;
//	right_stable(punsignedb,m+n);
//	delete []punsignedb;*/
}
/*typedef struct _SYSTEMTIME {  // st 
    WORD wYear; 
    WORD wMonth; 
    WORD wDayOfWeek; 
    WORD wDay; 
    WORD wHour; 
    WORD wMinute; 
    WORD wSecond; 
    WORD wMilliseconds; 
} SYSTEMTIME; 
*/