unstablemerge.cpp

一种快速二路归并算法

#include <windows.h>
#include <winbase.h>
#include <mmsystem.h>
#include <iostream.h>
#include <iomanip.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
//double count_com=0,count_mov=0;
class eletype
{
public:
	long num;
	long value;
	void succ()//关键字加1
	{
		value++;
	}
	void pred()//关键字减1
	{
		value--;
	}

	void operator+(long i)//重载加法，加关键字
	{
		value+=i;
	}

	long operator-(eletype t)//重载减法，减关键字
	{
		return value-t.value;
	}

	//重载比较运算符，对元素关键字进行比较
	bool operator<(eletype second)
	{
		return value<second.value;
	}
	bool operator==(eletype second)
	{
		return value==second.value;
	}
	bool operator<=(eletype second)
	{
		return value<=second.value;
	}
	bool operator>=(eletype second)
	{
		return value>=second.value;
	}
	bool operator>(eletype second)
	{
		return value>second.value;
	}
	bool operator!=(eletype second)
	{
		return value!=second.value;
	}
};

void exchange(eletype *punsigned,long i,long j)//交换位置i和位置j的元素
{
	eletype temp;
	temp=*(punsigned+i);
	*(punsigned+i)=*(punsigned+j);
	*(punsigned+j)=temp;
////count_mov+=3;
}
//二分搜索大于目标的第一个元素的位置
long binarysearchgreat(eletype *punsigned,long firstpos,long endpos,long target)
{
	long mid;
	do
	{
////		count_com++;
		mid=(firstpos+endpos)/2;
		if(*(punsigned+target)>=*(punsigned+mid))
			firstpos=mid+1;
		else
			endpos=mid-1;
	}while(firstpos<=endpos);
////	count_com++;
	if(*(punsigned+target)>=*(punsigned+mid))
		return mid+1;
	else
		return mid;
}
//二分搜索不小于目标的第一个元素的位置

long binarysearchle(eletype *punsigned,long firstpos,long endpos,long target)
{
	long mid;
	do
	{
////		count_com++;
		mid=(firstpos+endpos)/2;
		if(*(punsigned+target)>*(punsigned+mid))
			firstpos=mid+1;
		else
			endpos=mid-1;
	}while(firstpos<=endpos);
////	count_com++;
	if(*(punsigned+target)>*(punsigned+mid))
		return mid+1;
	else
		return mid;
}//选择排序
void selectsort(eletype *punsigned,long firstpos,long endpos)
{
	long minpos;
	for(long i=firstpos;i<endpos;i++)
	{
		minpos=i;
		for(long j=i+1;j<=endpos;j++)
			if(*(punsigned+j)<*(punsigned+minpos))
				minpos=j;
		if(minpos!=i)
			exchange(punsigned,i,minpos);
	}
}


void copyunsigneda(eletype *p1,eletype *p2,long n)
{
	for(long i=0;i<n;i++)
		*(p2+i)=*(p1+i);
}

void input(eletype *punsigned,long n)
{
	for(long t=0;t<n;t++)
	{
		(punsigned+t)->num=t;
		(punsigned+t)->value=rand();
	}
	for(t=0;t<n-1;t++)
		(punsigned+t)->value*=(punsigned+t+1)->value;
}
void output(eletype *punsigned,long n)
{
	char ch;
	cout<<"已排序序列为："<<endl;
	for(long t=0;t<n;t++)
//	for(long t=75;t<94;t++)
	{
		if(t%96==0)
			cin>>ch;
		if(t%4==0)
			cout<<endl;
		cout<<setw(7)<<(punsigned+t)->num<<":"<<setw(10)<<(punsigned+t)->value<<" ";
	}
	cout<<endl;
	cin>>ch;
}

void right_stable(eletype *punsigned,long n)
{
	char ch;
	long wrong=0,notstable=0;
	for(long t=0;t<n-1;t++)
	{
		if((punsigned+t)->value>(punsigned+t+1)->value)
		{
			wrong++;
			cout<<(punsigned+t)->num<<":"<<setw(8)<<(punsigned+t)->value<<" ";
			cout<<(punsigned+t+1)->num<<":"<<setw(8)<<(punsigned+t+1)->value<<" "<<endl;
			cin>>ch;
		}
		else if((punsigned+t)->value==(punsigned+t+1)->value &&(punsigned+t)->num>(punsigned+t+1)->num)
		{
			notstable++;
//			cout<<(punsigned+t)->num<<":"<<setw(8)<<(punsigned+t)->value<<" ";
//			cout<<(punsigned+t+1)->num<<":"<<setw(8)<<(punsigned+t+1)->value<<" "<<endl;
//			cin>>ch;
		}
	}
	cout<<endl;
	if(wrong)
		cout<<"排序不正确！！！"<<endl;
	else
		cout<<"排序正确！！！"<<endl;
	if(notstable)
		cout<<"排序不稳定！！！"<<endl;
	else
		cout<<"排序稳定！！！"<<endl;
//	cin>>ch;
}

//直接插入归并排序
void merge(eletype *punsigned,long firstpos,long divid,long endpos)
{
	long i=firstpos,j=divid+1;
	eletype temp;
	while(i<=divid &&j<=endpos)
	{
		if(*(punsigned+i)<=*(punsigned+j))
		{i++;}////count_com++;
		else
		{
//			count_com++;
			temp=*(punsigned+j);////count_mov++;
			for(long t=j-1;t>=i;t--)
			{*(punsigned+t+1)=*(punsigned+t);}////count_mov++;
			*(punsigned+i)=temp;////count_mov++;
			i++;j++;divid++;
		}
	}
}

//求m和n的最大公约数
long maxgen(long m,long n)
{
//cout<<endl<<"m="<<m<<",n="<<n<<endl;
	long k;
	if(m<n)
	{
		k=m;
		m=n;
		n=k;
	}
	k=m%n;
	while(k!=0)
	{
		m=n;
		n=k;
		k=m%n;
	}
	return n;
}

//交换相邻数据块
void adjacentblockexchange(eletype *p,long firstpos,long divid,long endpos)
{
	long t;
	long len1=divid-firstpos+1;
	long len2=endpos-divid;
	long dis=len2;
	long gen=maxgen(len1,len2);//环个数

	for(long i=0;i<gen;i++)
	{
		eletype temp=*(p+firstpos+i);////count_mov++;
		long j;
		t=firstpos+i;
		j=divid+1+i;
		while(j!=firstpos+i)
		{
			*(p+t)=*(p+j);////count_mov++;
			t=j;
			j=(j-dis)>=firstpos?(j-dis):(j-dis+len1+len2);
		}
		*(p+t)=temp;////count_mov++;
	}

}
//交换等长数据块，两数据块不必邻接
void equalsizeblockexchange(eletype *punsigned,long firstpos,long secondpos,long len)  
{
	eletype t;
	for(long i=0;i<len;i++)
	{
		t=*(punsigned+firstpos+i);
		*(punsigned+firstpos+i)=*(punsigned+secondpos+i);
		*(punsigned+secondpos+i)=t;
	}
////count_mov+=3*len;

}
//快速排序
void quicksort(eletype *punsigned,long firstpos,long divid,long endpos)
{
	long i=divid-1,j=divid+1;
	while(j<=endpos &&*(punsigned+divid)>*(punsigned+j))
		j++;
	while(i>=firstpos&&*(punsigned+divid)==*(punsigned+i))
		i--;
	if(j>divid+1)
	{
		adjacentblockexchange(punsigned,i+1,divid,j-1);
		if(i>=firstpos&&j-1>=divid+1)
			quicksort(punsigned,firstpos,i,i+j-1-divid);
	}
}
//堆排序的筛选函数
void  sift(eletype *punsigned,long firstpos,long endpos)
{
	long i=firstpos,j=2*i+1;
	eletype t=*(punsigned+i);
	bool finished=false;
	while(j<=endpos && !finished)
	{
		if(j<endpos && *(punsigned+j)<=*(punsigned+j+1))
			j++;
		if(t>*(punsigned+j))
			finished=true;
		else
		{
			*(punsigned+i)=*(punsigned+j);
			i=j,j=i*2+1;
		}
	}
	*(punsigned+i)=t;
}
void heapsort(eletype *punsigned,long n)
{
	for(int i=(n+1)/2-1;i>=0;i--)
		sift(punsigned,i,n-1);
	for(i=n-1;i>=1;i--)
	{
		exchange(punsigned,0,i);
		//此处添加代码使其稳定？
		sift(punsigned,0,i-1);
	}
}
//缓冲元素在最后时归并缓冲元素
void mergebufferelementfromend(eletype *punsigned,long firstpos,long divid,long endpos)//缓冲在最后
{
	long buflen=endpos-divid;
	long j=endpos,i=divid;
	while(buflen>0)//缓冲元素未归并完
	{
//		cout<<i<<j<<endl;
		while(i>=firstpos && *(punsigned+i)>*(punsigned+j))
		{i--;}////count_com++;
		if(i>=firstpos && i<divid )//*(punsigned+i)<=*(punsigned+j),*(punsigned+i+1)>*(punsigned+j)
		{
			adjacentblockexchange(punsigned,i+1,divid,j);
			buflen--;
			divid=i;
			j=i+buflen;
		}
		else if(i<firstpos)//缓冲元素全小
		{
			adjacentblockexchange(punsigned,firstpos,divid,j);
			return;
		}
		else//i==divid,*(punsigned+i)<=*(punsigned+j),当前缓冲元素大
		{
			j--;
			buflen--;
		}
	}
}
//缓冲元素在最前时归并缓冲元素
void mergebufferelementfromfirst(eletype *punsigned,long firstpos,long divid,long endpos)//缓冲在最前
{
	long buflen=divid-firstpos+1;
	long j=divid+1,i=firstpos;
	while(buflen>0)//缓冲元素未归并完
	{
		while(j<=endpos && *(punsigned+i)>*(punsigned+j))
		{j++;}////count_com++;
		if(j<=endpos && j>divid+1)//*(punsigned+i)<=*(punsigned+j),*(punsigned+i)>*(punsigned+j-1)
		{
			adjacentblockexchange(punsigned,i,divid,j-1);
			buflen--;
			i=j-buflen;
			divid=j-1;
		}
		else if(j>endpos)//缓冲元素全大
		{
			adjacentblockexchange(punsigned,i,divid,endpos);
			return;
		}
		else//j==divid，*(punsigned+i)<=*(punsigned+j), 当前缓冲元素小
		{
			i++;
			buflen--;
		}
	}
}

void advancedmerge(eletype *punsigned,long firstpos,long divid,long endpos)
{
	if(firstpos>divid || endpos<=divid)
		return;
	else
	{
		long len1=divid-firstpos+1,len2=endpos-divid;
		double t=sqrt(len1+len2);
		long sqrtn=(long)(floor(t)==t?t:t+1);
		if(len2<=sqrtn)
			mergebufferelementfromend(punsigned,firstpos,divid,endpos);
		else if(len1<=sqrtn)
			mergebufferelementfromfirst(punsigned,firstpos,divid,endpos);
		else
		{
			long i=firstpos,j=divid+1;
			long lenoffirstblockoffirstsublist=(len1%sqrtn)?(len1%sqrtn):sqrtn;
			long lenoffirstblockofsecondsublist=(len2%sqrtn)?(len2%sqrtn):sqrtn;
			long ii=i+lenoffirstblockoffirstsublist-1;