内部排序.cpp

数据结构课程设计

#include<iostream.h>
#include <stdio.h>
#include<windows.h>
#define MAX 1000
int jj,n[6]={0,0},c[6]={0,0}; 
class paixu
{
  public:
	    void XuanzePaixu();//简单选择排序
		void MaopaoPaixu();//冒泡排序
		void CharuPaixu();//直接插入排序
		//快速排序
		int  Huafen(int l,int h);
		void KPaixu(int l,int h);
		void KuaisuPaixu();
		//堆排序
		void dui(int s,int m);
		void DuiPaixu();
		
		void XierPaixu();//希尔排序
		void suijishu(int y);//产生随机数
  private:
	  int RA1[MAX],RA2[MAX];
};

//==============================================================================
//简单选择排序
void paixu::XuanzePaixu() 
{
	int v;
	for(int i=1;i <= jj;i++)
	{RA2[i] = RA1[i];n[0]++;}
	for( i = 1 ; i < jj ; ++i)
	{
		int j = i;
		for(int k = i+1 ; k <= jj ; k++)
		{	if(RA2[k] < RA2[j]) j = k;c[0]++;}
			if(i != j)
			{	v = RA2[j];	
			    RA2[j] = RA2[i]; 
			    RA2[i] = v; 
				n[0]++;
			} 
    
	} cout<<"排序后的元素为:"<<endl;
	 for( i=1;i <= jj;i++)
		 cout<<RA2[i]<<"  ";
	 cout<<endl;
	 cout<<"比较次数为："<<c[0];
	 cout<<"移动次数为："<<n[0];
} 
//==============================================================================
//起泡排序
void paixu::MaopaoPaixu()
{
	int k=jj;
	int w;
	for(int i=1;i <= jj;i++)
	{RA2[i] = RA1[i];n[1]++;}
	while(k>1)
	{
	int	Index=1;
		for(int j=1;j<k;j++)
		{
			if(RA2[j+1]<RA2[j])
			{
			  w=RA2[j];
			  RA2[j]=RA2[j+1];
			  RA2[j+1]=w;      //互换记录
			  Index=j;
			  n[1]++;
			} 
			c[1]++;
		}k=Index;
	}
	 cout<<"排序后的元素为:"<<endl;
	 for( i=1;i <= jj;i++)
		 cout<<RA2[i]<<"  ";
	 cout<<endl;
	 cout<<"比较次数为："<<c[1];
	 cout<<"移动次数为："<<n[1];
	 
}
//==============================================================================
//直接插入排序
void paixu::CharuPaixu()
{
    
	for(int i=1;i <= jj;i++)
	{RA2[i] = RA1[i];}
	for(i=2;i<=jj;++i)
	   if(RA2[i]<RA2[i-1])
	   {
	    RA2[0]=RA2[i];  //复制为哨兵
		for(int j=i-1;RA2[0]<RA2[j];--j)
		{RA2[j+1]=RA2[j]; n[2]++;c[2]++;}//记录后移
		    RA2[j+1]=RA2[0];  //插入到正确位置
		    n[2]++;
	   }
	        n[2]++;
			c[2]++;
     cout<<"排序后的元素为:"<<endl;
	 for( i=1;i <= jj;i++)
		 cout<<RA2[i]<<"  ";
	 cout<<endl;
	 cout<<"移动次数为："<<c[2];
	 cout<<"一共移动次数为："<<n[2];
}
//==============================================================================
//快速排序
int paixu::Huafen(int l,int h) //划分
{
	RA2[0] = RA2[l];    
	int pt = RA2[l];  //枢轴记录关键字
	while(l < h)         //从表的两端交替地向中间扫描
	{
		while(l < h && RA2[h] >= pt) {-- h;c[3]++;}
		RA2[l] = RA2[h];c[3]++;n[3]++;    //将比枢轴记录小的记录移到底端
		while (l < h && RA2[l] <= pt) {++ l;c[3]++;}
		RA2[h] = RA2[l];n[3]++;c[3]++;   //将比枢轴记录大的记录移到高端
	}// while
	RA2[l] = RA2[0];     //枢轴记录移到正确位置
	n[3]++;
	return l;        //返回枢轴的位置
} //Huafen
void paixu::KPaixu(int l,int h)
{
	if(l < h)   //长度大于1
	{
		int pivotloc = Huafen(l,h); 
	    KPaixu(l,pivotloc-1);   //对底端子序列递归排序
		KPaixu(pivotloc+1,h);   //对高断子序列递归排序
	} //if
}// KuaisuPaixu
void paixu::KuaisuPaixu() //快速排序
{   
	for(int i=1;i <= jj;i++)
	{RA2[i] = RA1[i];}
	KPaixu(1,jj);
	cout<<"排序后的元素为:"<<endl;
	 for(i=1;i <= jj;i++)
		 cout<<RA2[i]<<"  ";
	 cout<<endl;
	 cout<<"比较次数为："<<c[3]<<"      ";
	 cout<<"移动次数为："<<n[3];
} //KuaisuPaixu
//==============================================================================
//堆排序
void paixu::dui(int s,int m)
{   
	for(int i=1;i <= jj;i++)
	{RA2[i] = RA1[i];}
	int rc = RA2[s];       //暂存根结点的记录
	for(int j = 2*s;j<=m;j*=2)  //沿较大的孩子结点向下筛选
	{
		if(j<m&&RA2[j]<RA2[j+1])++j; c[4]++;
		if(RA2[s]>=RA2[j]){c[4]++;break;  }      //不需要调整
		RA2[s] = RA2[j];
		n[4]++;//把大于关键字记录往上调	
		s = j;
	}
	RA2[s] = rc;n[4]++;     //回移筛选小的记录
}
void paixu::DuiPaixu()
{
	int w;
	for(int i = jj/2;i>0;--i)  
		dui(i,jj);
	    w = RA2[1];
	   RA2[1] = RA2[jj];
	   RA2[jj] = w;
	//交换"堆顶"和"堆底"的记录
	for(i = jj-1;i>1;--i)
	{
		dui(1,i);   
		w = RA2[1];RA2[1] = RA2[i];RA2[i] = w; 
		//将堆顶记录和当前的"堆底"记录相互交换使已有序的记录堆移到底部
	}
	cout<<"排序后的元素为:"<<endl;
	 for( i=1;i <= jj;i++)
		 cout<<RA2[i]<<"  ";
	 cout<<endl;
	 cout<<"比较次数为："<<c[4]<<"      ";
	 cout<<"移动次数为："<<n[4];

}
//==============================================================================
//希尔排序

void paixu::XierPaixu()
{
	for(int i=1;i <= jj;i++)
	{RA2[i] = RA1[i];}
	int dt=5;
   	do
	{
		dt = dt/3+1;
	//1 前后记录位置的增量是dt，而不是1
	for(int i=dt+1;i<=jj;++i)
		if(RA2[i]<RA2[i-dt]){ c[5]++;         //需将RA2.[i]插入有序增量子表
		  RA2[0]=RA2[i];               //暂存在RA2.[0]
			n[5]++;
		  int j=i-dt;
			do
			{
				RA2[j+dt] = RA2[j];n[5]++;
				j = j - dt;
				c[5]++;
			}while(j > 0&&RA2[0] < RA2[j]); //记录后移，查找插入位置
			RA2[j+dt]=RA2[0];n[5]++;c[5]++; //插入
		}
	}while(dt > 1);
	cout<<"排序后的元素为:"<<endl;
	 for( i=1;i <= jj;i++)
		 cout<<RA2[i]<<"  ";
	 cout<<endl;
	 cout<<"比较次数为："<<c[5]<<"      ";
	 cout<<"移动次数为："<<n[5];

}//XierPaixu//一趟增量为dt[k]的插入排序
//==============================================================================
//随机生成函数
void paixu::suijishu(int y)
	  {
         int i;
         for(i=1;i<=y;i++)
         RA1[i]=(int)rand();
		 cout<<"随机产生的所有元素为:"<<endl;
		 for(i=1;i<=y;i++)
			 cout<<RA1[i]<<"   ";
		 cout<<endl;
	  }
void main()
{           
	paixu m;
cc:	system("cls");
	cout<<"     ◆◆◆◆内部排序算法比较程序◆◆◆◆"<<endl<<endl;
	cout<<"     ***********************************\t"<<endl;
	cout<<"     *\t         1、内部排序比较       *\t"<<endl;
	cout<<"     *\t         2、退出系统           *\t"<<endl;
	cout<<"     ***********************************\t"<<endl;
	char b;
dt:	cin>>b;
	if(b == '1')
	{
	system("cls");
	cout<<"------------------------------------------------"<<endl;
	cout<<"     \t         ⊙返回上页            \t"<<endl;
	cout<<"     \t         ①简单选择排序        \t"<<endl;
	cout<<"     \t         ②起泡排序            \t"<<endl;
	cout<<"     \t         ③直接插入排序        \t"<<endl;
	cout<<"     \t         ④快速排序            \t"<<endl;
	cout<<"     \t         ⑤堆排序              \t"<<endl;
	cout<<"     \t         ⑥希尔排序            \t"<<endl;
	cout<<"请输入要处理的1组随机数的总个数: ";
	int q;
	cin>>q;
	system("cls");
	if(q==0)
	goto cc;
	jj=q;
	m.suijishu(q);
	cout<<endl;
	while(1)
	{
	cout<<"------------------------------------------------"<<endl;
	cout<<"     \t         ⊙返回上页            \t"<<endl;
	cout<<"     \t         ①简单选择排序        \t"<<endl;
	cout<<"     \t         ②起泡排序            \t"<<endl;
	cout<<"     \t         ③直接插入排序        \t"<<endl;
	cout<<"     \t         ④快速排序            \t"<<endl;
	cout<<"     \t         ⑤堆排序              \t"<<endl;
	cout<<"     \t         ⑥希尔排序            \t"<<endl;
	char k;
	cout<<"请选择你要排序的方法：";
	cin>>k;
	switch(k) 
	{ 
		case '0':   
			        goto cc;
		case '1':
					m.XuanzePaixu();
				
					break; 
		case '2':
					m.MaopaoPaixu();
				
					break;
		case '3':    
					m.CharuPaixu();
				
					break; 
		case '4':
					m.KuaisuPaixu();
				
					break;
		case '5':   
					m.DuiPaixu();
				
					break;
		case '6':   
					m.XierPaixu();
				
					break;
		default:
					cout<<"输入信息错误！请重新输入！"<<endl;
					break;
	}//switch
	               	cout<<endl;
					cout<<"按任意键返回！"<<endl;
					getchar();
                    system("cls");
	} 
	}
	if(b == '2')
		  exit(0);
	else
		  cout<<"输入信息错误！请重新输入:"<<endl;
		  goto dt;
}