cintercmp.h

这个程序包括了各种常用内部排序算法在平均排序所需时间上的比较.

void CBubbleSort::bubblepass(int i)
{
	flag=true;
	for(int j=1;j<i;j++)
	{
		if(rand_data[j]>rand_data[j+1])
		{
			int tem=rand_data[j];
			rand_data[j]=rand_data[j+1];
			rand_data[j+1]=tem;
			flag=false;
			move_time+=3;
		}
		cmp_time++;
	}
  
}

////////////////////////////////////////
void CBubbleSort::bubblesort()
{
   for(int i=n;i>=2;i--)
   {
	   bubblepass(i);
	   if((flag)||(i==2))
		   break;
   }
}
//////////////////////////////////////////
void CBubbleSort::BootFromFile()
{
	FILE *fp;
	if((fp=fopen("test.txt","r"))==NULL)
	{
		cout<<"文件不能打开!"<<endl;
		exit(0);
	}
	fscanf(fp,"此文件的记录个数是:%d",&n);
	for(int i=1;i<=n;i++)
		fscanf(fp,"%d\n",&(rand_data[i]));
	fclose(fp);
}
////////////////////////////////////////
void CBubbleSort::SaveRandData()
{
	int i;  
    time_t t;  
    srand((unsigned) time(&t)); 
	FILE *fp;
	if((fp=fopen("test.txt","w"))==NULL)
	{
		cout<<"文件不能打开!"<<endl;
		exit(0);
	}
	fprintf(fp,"此文件的记录个数是:200\n");
	for(i=1;i<=200;i++)
	    fprintf(fp,"%d\n",rand()%100);
	fclose(fp);
}
///////////////////////////////////////////
/////////////////////////////////////////////////////
void CBubbleSort::DisplayOrginal()
{
	cout<<"原来的序列是:\n";
	for(int i=1;i<=n;i++)
	{
		cout<<rand_data[i]<<" ";
		if(!(i%10))
			cout<<endl;
	}
	cout<<endl;
}

/////////////////////////////////////////////////////
void CBubbleSort::DisplayNew()
{
	cout<<"排序后的序列是:\n";
	for(int i=1;i<=n;i++)
	{
		cout<<rand_data[i]<<" ";
		if(!(i%10))
			cout<<endl;
	}
	cout<<endl;
}
///////////////////////////////////////////
void CBubbleSort::Deal()
{
    //SaveRandData();
	BootFromFile();
	move_time=0;//初始化
	cmp_time=0;//初始化
	DisplayOrginal();
	bubblesort();
	DisplayNew();
	cout<<"移动的次数:"<<move_time<<endl;
	cout<<"比较的次数:"<<cmp_time<<endl;
}
///////////////////////////////////////////
void CBubbleSort::Deal1()
{
    //SaveRandData();
	BootFromFile();
	move_time=0;//初始化
	cmp_time=0;//初始化
	bubblesort();
}
//希尔排序
class CShellSort
{
	public:
		typedef struct //定义排序表的结构
		{
	       int elemword[MAXSIZE]; //数据元素关键字
           int count; //表中当前元素的个数
		}SqList;
	int move_time;//移动的次数
	int cmp_time;//比较的次数
    void InitialSqList(SqList&); //初始化排序表
    void ShellSort(SqList &,int [],int);//希尔排序 
    void ShellInsert(SqList&,int); //一趟希尔排序
    void DealShellSort();
	void DealShellSort1();
    void PrintSqListOrig(SqList); //显示表中排序前的所有元素
    void PrintSqListNow(SqList); //显示表中排序后的所有元素
};
void CShellSort::DealShellSort()
{
	SqList L; //声明表L
    int dlta[3]={5,3,1}; //希尔排序增量序列，本程序采用5，3，1序列
    int t=3; //希尔排序增量序列中增量的个数 
	cmp_time=0;
	move_time=0;
    InitialSqList(L); //待排序列初始化
    PrintSqListOrig(L);//显示表中排序前的所有元素
    ShellSort(L,dlta,t); //希尔排序
    PrintSqListNow(L); //显示希尔排序结果
	cout<<"移动的次数:"<<move_time<<endl;
	cout<<"比较的次数:"<<cmp_time<<endl;
}
void CShellSort::DealShellSort1()
{
	SqList L; //声明表L
    int dlta[3]={5,3,1}; //希尔排序增量序列，本程序采用5，3，1序列
    int t=3; //希尔排序增量序列中增量的个数 
	cmp_time=0;
	move_time=0;
    InitialSqList(L); //待排序列初始化
    ShellSort(L,dlta,t); //希尔排序
}
void CShellSort::InitialSqList(SqList &L)
{
	//表初始化
	FILE *fp;
	if((fp=fopen("test.txt","r"))==NULL)
	{
		printf("文件不能打开!\n");
		exit(0);
	}
    int i;
    fscanf(fp,"此文件的记录个数是:%d",&L.count);
    for(i=1;i<=L.count;i++)
		fscanf(fp,"%d\n",&L.elemword[i]);
	fclose(fp);
}
void CShellSort::ShellSort(SqList &L,int dlta[],int t)
{
	//按增量序列dlta[0..t-1]对顺序表L作希尔排序
    for(int k=0;k<t;++k)
        ShellInsert(L,dlta[k]); //一趟增量为dlta[k]的插入排序
}
void CShellSort::ShellInsert(SqList &L,int dk)
{
	//对顺序表L做一趟希尔插入排序。本算法是和一趟直接插入排序相比，作了以下修改：
    //1. 前后记录的增量是dk，而不是1
    //2. 0号单元只是暂存单元，不是哨兵。当j<=0时，插入位置已找到
    int i,j;
    for(i=dk+1;i<=L.count;i++)
	{
	   cmp_time++;
       if(L.elemword[i]<L.elemword[i-dk]) //"<",需将L.elemword[i]插入有序子表
	   { 
		  L.elemword[0]=L.elemword[i]; //暂存在0号单元
		  move_time++;
          for(j=i-dk;j>0&&L.elemword[0]<L.elemword[j];j-=dk)
		  {
             L.elemword[j+dk]=L.elemword[j]; //记录后移，查找插入位置
		     move_time++;
		  } 
          L.elemword[j+dk]=L.elemword[0]; //插入到正确的位置
		  move_time++;
	   }
	}
}
///////////////////////////////////////////////////////////////
void CShellSort::PrintSqListOrig(SqList L)
{  
	//显示表中所有元素
    int i;
    printf("原来的序列如下：\n");
    for(i=1;i<=L.count;i++)
	{
       printf("%4d",L.elemword[i]);
	   if(!(i%10))
		   printf("\n");
	}
    printf("\n");
}
void CShellSort::PrintSqListNow(SqList L)
{
	//显示表中所有元素
    int i;
    printf("现在的序列如下：\n");
    for(i=1;i<=L.count;i++)
	{
       printf("%4d",L.elemword[i]);
	   if(!(i%10))
		   printf("\n");
	}
    printf("\n");
}
///////////////////////////////////////////////////////////////
//归并排序
class CMergeSort
{
	public:
	       typedef struct //定义排序表的结构
		   {
	          int elemword[MAXSIZE]; //数据元素关键字
              int length; //表中当前元素的个数
		   }SqList;
    void InitialSqList(SqList&); //初始化排序表
    void MergeSort(SqList &); //归并排序
    void MSort(int [],int [],int,int); //归并排序递归子程序
    void Merge(int [],int [],int,int,int); //两个子序列归并
    void DealMergeSort();
    void PrintSqListOrig(SqList); //显示表中排序前的所有元素
    void PrintSqListNow(SqList); //显示表中排序后的所有元素
	void DealMergeSort1();
	int Move_Time;//移动的次数
    int Cmp_Time;//比较的次数
};
void CMergeSort::DealMergeSort()
{
	SqList L; 
    InitialSqList(L); //待排序列初始化
    Move_Time=0;//移动的次数
    Cmp_Time=0;//比较的次数
    PrintSqListOrig(L);////显示表中排序前的所有元素
    MergeSort(L); //归并排序
    PrintSqListNow(L); //显示表中排序后的所有元素
	printf("移动的次数:%d\n",Move_Time);
	printf("比较的次数:%d\n",Cmp_Time);

}
void CMergeSort::DealMergeSort1()//只获得移动的次数和比较的次数就可以了
{
	SqList L; 
    InitialSqList(L); //待排序列初始化
    Move_Time=0;//移动的次数
    Cmp_Time=0;//比较的次数
    MergeSort(L); //归并排序
}
//////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////
void CMergeSort::InitialSqList(SqList &L)//表初始化(从文件中读入)
{
    FILE *fp;
	if((fp=fopen("test.txt","r"))==NULL)
	{
		printf("文件不能打开!\n");
		exit(0);
	}
    int i;
    fscanf(fp,"此文件的记录个数是:%d",&L.length);
    for(i=1;i<=L.length;i++)
		fscanf(fp,"%d\n",&L.elemword[i]);
	fclose(fp);
}
////////////////////////////////////////////////////////////
void CMergeSort::MergeSort(SqList &L)
{
	//对顺序表L做归并排序。
    MSort(L.elemword,L.elemword,1,L.length);
}
////////////////////////////////////////////////////////////
void CMergeSort::MSort(int SR[],int TR1[],int s,int t)
{
	//将SR[s..t]归并排序为TR1[s..t]。
    int m;
    int TR2[MAXSIZE];
    if(s==t)
	{
		TR1[s]=SR[s];
		Move_Time++;
	}

    else
	{
		m=(s+t)/2; //将SR[s..t]平分为SR[s..m]和SR[m+1..t]
        MSort(SR,TR2,s,m); //递归地将SR[s..m]归并为有序的TR2[s..m]
        MSort(SR,TR2,m+1,t); //递归地将SR[m+1..t]归并为有序的TR2[m+1..t]
        Merge(TR2,TR1,s,m,t);//将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]
	}
}
/////////////////////////////////////////////////////////////
void CMergeSort::Merge(int SR[],int TR[],int i,int m,int n)
{
	//将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]
    int j,k,p;
    for(j=m+1,k=i;i<=m&&j<=n;++k) //将SR中的记录有小到大地并入TR
	{
        Cmp_Time++;
		if(SR[i]<SR[j]) 
		{
			TR[k]=SR[i++];
			Cmp_Time++;
		    Move_Time++;
		}
        else 
		{
			TR[k]=SR[j++];
			Cmp_Time++;
			Move_Time++;
		}
	}
    if(i<=m)
      for(p=k;p<=n;p++) //将剩余的SR[i..m]复制到TR
	  {
		  TR[p]=SR[i];
		  Move_Time++;
          i++;
	  }
    if(j<=n)
      for(p=k;p<=n;p++) //将剩余的SR[j..n]复制到TR
	  {
		  TR[p]=SR[j];
		  Move_Time++;
          j++;
	  }
}
///////////////////////////////////////////////////////////////
void CMergeSort::PrintSqListOrig(SqList L)
{  
	//显示表中所有元素
    int i;
    printf("原来的序列如下：\n");
    for(i=1;i<=L.length;i++)
	{
       printf("%4d",L.elemword[i]);
	   if(!(i%10))
		   printf("\n");
	}
    printf("\n");
}
void CMergeSort::PrintSqListNow(SqList L)
{
	//显示表中所有元素
    int i;
    printf("现在的序列如下：\n");
    for(i=1;i<=L.length;i++)
    {
       printf("%4d",L.elemword[i]);
	   if(!(i%10))
		   printf("\n");
	}
    printf("\n");
} 
//////////////////////////////////////////
//基数排序
class CRadixSort
{
	public:
          int n;//接收的记录数
          int d;//关键字包含的位数
          int p;
          int f[10],e[10];
          int move_time;//移动的次数
          int cmp_time;//比较的次数
          struct rcdnode
		  {
	         int key[10];
	         int next;
		  }r[200];
	void BootFromFile();
    void distribute(int,int);
    void collect(int);//,int&
    void radixsort();//int&
    void DisplayOrginal();
    void DisplayNew();
    void DealRadix();
	void DealRadix1();
};
////////////////////////////////////////////
void CRadixSort::BootFromFile()
{
	FILE *fp;
	char ch;
	int j;
	if((fp=fopen("test.txt","r"))==NULL)
	{
		cout<<"文件不能打开!"<<endl;
		exit(0);
	}
	fscanf(fp,"此文件的记录个数是:%d\n",&n);
	for(int i=1;i<=n;i++)
	{
		j=1;
		while((ch=fgetc(fp))!='\n')
		{
			r[i].key[j]=ch-48;
			j++;
		}
		r[i].key[j]='a';
	}
	fclose(fp);
}
/////////////////////////////////////////////////////////////////
void CRadixSort::distribute(int p,int i)
{
	int p1=p;
	for(int j=0;j<=9;j++)
		f[j]=0;
    cmp_time++;
	while(p1!=0)
	{
		j=r[p1].key[i];
		//cout<<j<<endl;
		//cout<<i<<endl;
		//cout<<p1<<endl;
        cmp_time++;
		if(f[j]==0)
			f[j]=p1;
		else
			r[e[j]].next=p1;
		e[j]=p1;
		p1=r[p1].next;
	}
}
///////////////////////////////////////////////////////////////////
void CRadixSort::collect(int i)//,int &p
{
	int j=0,t;
	cmp_time++;
	while(f[j]==0)
	{
		j++;
		cmp_time++;
	}
	p=f[j];
	t=e[j];
	cmp_time++;
    while(j<9)
	{
		j++;
		cmp_time++;
		while((j<9)&&(f[j]==0))
		{
			j++;
			cmp_time++;
		}
		cmp_time++;
		if(f[j]!=0)
		{
			r[t].next=f[j];
			t=e[j];
		}
	}
	r[t].next=0;
}
//////////////////////////////////////////////////////////////////////
void CRadixSort::radixsort()//int &p
{
	//cout<<r[1].key[3]<<endl;
	for(int i=1;i<=n-1;i++)
		r[i].next=i+1;
	r[n].next=0;
	//cout<<r[n].key[3]<<endl;
	//p=1;

	for(i=d;i>=1;i--)//现在d=3
	{
		distribute(p,i);
		collect(i);
	}
}
/////////////////////////////////////////////////////////////////////////
void CRadixSort::DisplayOrginal()
{
	cout<<"原来的序列是:\n";
	for(int i=1;i<=n;i++)
	{
		int j=1;
		while(r[i].key[j]!='a')//a是结束的标志
		{
			cout<<r[i].key[j];
			j++;
		}
		cout<<"  ";
		if(!(i%10))
			cout<<endl;
	}
	cout<<endl;
}

/////////////////////////////////////////////////////
void CRadixSort::DisplayNew()
{
	cout<<"排序后的序列是:\n";
	int i=0;
	while(p!=0)
	{
		int j=1;
		while(r[p].key[j]!='a')//a是结束的标志
		{
			cout<<r[p].key[j];
			j++;
		}
		cout<<"  ";
		p=r[p].next;
		i++;
        if(!(i%10))
			cout<<endl;
	}
	cout<<endl;
}
///////////////////////////////////////////
void CRadixSort::DealRadix()
{
	d=3;
	p=1;
    move_time=0;//移动的次数
    cmp_time=0;//比较的次数
	BootFromFile();
	DisplayOrginal();
    radixsort();
	DisplayNew();
    cout<<"移动的次数:"<<move_time<<endl;
	cout<<"比较的次数:"<<cmp_time<<endl;
}
///////////////////////////////////////////
void CRadixSort::DealRadix1()
{
	d=3;
	p=1;
    move_time=0;//移动的次数
    cmp_time=0;//比较的次数
	BootFromFile();
    radixsort();
}
	
//////////////////////////////////////////
//////////////////////////////////////////
//2-路插入排序
class CTwoWayInsertSort
{
	public:
	int n;//要进行排序的随机数的个数
    int r[10000],d[10000];
	int move_time;//移动的次数
	int cmp_time;//比较的次数
	int first,final;
	void TwoWayInsertSort();
	void DisplayOrginal();
	void DisplayNew();
	void BootFromFile();
	void Deal();
	void Deal1();
};
//////////////////////////////////////////
void CTwoWayInsertSort::TwoWayInsertSort()
{
    move_time++;
	d[0]=r[0];
	for(int i=1;i<n;i++)
	{
		cmp_time++;
		if(r[i]<r[0])
		{
			cmp_time++;
			for(int j=first+1;j<n;j++)
			{
				cmp_time++;
				if(d[j]<r[i])
				{
					d[j-1]=d[j];
					move_time++;
				}
				else
					break;
			}
			cmp_time++;
			d[j-1]=r[i];
			move_time++;
            first--;
		}
		else
		{
			for(int j=final-1;j>=0;j--)
			{
				cmp_time++;
				if(d[j]>r[i])
				{
					d[j+1]=d[j];
					move_time++;
				}
				else
					break;
			}
			d[j+1]=r[i];
			move_time++;
			final++;
		}
	}
}

////////////////////////////////////////
void CTwoWayInsertSort::BootFromFile()
{
	FILE *fp;
	if((fp=fopen("test.txt","r"))==NULL)
	{
		cout<<"文件不能打开!"<<endl;
		exit(0);
	}
	fscanf(fp,"此文件的记录个数是:%d",&n);
	for(int i=0;i<n;i++)
		fscanf(fp,"%d\n",&(r[i]));
	fclose(fp);
}

/////////////////////////////////////////////////////
void CTwoWayInsertSort::DisplayOrginal()
{
	cout<<"原来的序列是:\n";
	int count=0;
	for(int i=0;i<n;i++)
	{
		cout<<r[i]<<" ";
		count++;
		if(!(count%10))
			cout<<endl;
	}
	cout<<endl;
}

/////////////////////////////////////////////////////
void CTwoWayInsertSort::DisplayNew()
{
	cout<<"排序后的序列是:\n";
	int count=0;
	for(int i=first+1;i<n;i++)
	{
		cout<<d[i]<<"  ";
		count++;
		if(!(count%10))
			cout<<endl;
	}
	for(i=0;i<final;i++)
	{
		cout<<d[i]<<"  ";
		count++;
		if(!(count%10))
			cout<<endl;
	}
	cout<<endl;
}
///////////////////////////////////////////
void CTwoWayInsertSort::Deal()
{
	BootFromFile();
	first=n-1;
	final=1;
	move_time=0;//初始化
	cmp_time=0;//初始化
	DisplayOrginal();
	TwoWayInsertSort();
	DisplayNew();
	cout<<"移动的次数:"<<move_time<<endl;
	cout<<"比较的次数:"<<cmp_time<<endl;
}
//////////////////////////////////////////////////////////
void CTwoWayInsertSort::Deal1()
{
	BootFromFile();
	first=n-1;
	final=1;
	move_time=0;//初始化
	cmp_time=0;//初始化
	TwoWayInsertSort();
}
//////////////////////////////////////////////////////////