sorting.cpp

数据结构课程设计源码以及报告 有3个程序：1）哈弗曼树及哈弗曼编码 2）排序—内部排序方法 3）Hanoi Tower

# include <iostream.h>
# include <stdio.h>
# include <stdlib.h>
# include <windows.h>

#define Max 100000
typedef int RandomNum;
RandomNum Array1[Max];	//定义一个最大长度为Max的数组 Array1, 用来存放产生的伪随机数
RandomNum Array2[Max];	//定义一个空数组Array2
int AL;
int N1=0, N2=0, N3=0;
class Algorithms{
public:

	void Bubble(){
		for(int i=1; i<=AL; i++)
		{
			Array2[i]=Array1[i];
		}
		int M, N=0;
		int k=AL;
		while(k>1)
		{	int	lc=1;
			for(int j=1;j<k;j++)
				{
				if(Array2[j+1]<Array2[j])
					{	M=Array2[j];
						Array2[j]=Array2[j+1];
						Array2[j+1]=M;
						lc=j;
						N++;
					}
				}k=lc;
		}
		cout<<"\n经起泡排序得:\n";
		for(i=1; i<=AL; i++)
		{	cout<<Array2[i]<<" ";	}
		cout<<"\n总共需要移动"<<N<<"步";
		cout<<endl;
		getchar();
	}//----------Bubble--------------

	void StraightInsert(){					//p265
		int N=0;
		for(int i=1; i<=AL; i++)
		{ Array2[i]=Array1[i]; }
		  for( i=2;i<=AL;i++)
	   if(Array2[i]<Array2[i-1])
	   {	Array2[0]=Array2[i];				//Array2[0]为哨兵
		 for(int j=i-1;Array2[0]<Array2[j];--j)
			Array2[j+1]=Array2[j]; 			   //记录后移
			Array2[j+1]=Array2[0]; N++;
	   }
		cout<<"\n经直接插入排序得:\n";
		for(i=1; i<=AL; i++)
		{	cout<<Array2[i]<<" ";	}
		cout<<"\n总共需要移动"<<N<<"步";
		cout<<endl;
		getchar();
	}//---------------StraightInsert---------------

	void  Select(){				//p277
		int M, N=0;
		for(int i=1; i<=AL; i++)
		{ Array2[i]=Array1[i]; }
		for(i=1; i<AL; i++)
		{	int j=i;
			for(int k=i+1; k<=AL; k++)
			if(Array2[k]<Array2[j]) 
			{  j=k;	 }
			if(i!=j)
			{	M=Array2[j];	
				Array2[j]=Array2[i]; 
				Array2[i]=M;
				N++;
			} 
		}
		cout<<"\n经简单选择排序得:\n";
		for(i=1; i<=AL; i++)
		{	cout<<Array2[i]<<" ";	}
		cout<<"\n总共需要移动"<<N<<"步";
		cout<<endl;
		getchar();
	}//-----------------Select---------------

	int Partition(int low, int high ){		 //划分序列   p274
			Array2[0] = Array2[low];
			int pivotkey = Array2[low];
			while(low < high)         //从表的两端交替地向中间扫描
		{
			while(low < high && Array2[high] >= pivotkey){ -- high;
			Array2[low] = Array2[high]; N1++; }  //将比枢轴记录小的记录移到底端
			while (low < high && Array2[low] <= pivotkey){ ++ low;
			Array2[high] = Array2[low]; N1++; }  //将比枢轴记录大的记录移到高端
		}
			Array2[low] = Array2[0];     //枢轴记录移到正确位置
			return low;        //返回枢轴的位置
		}
	void QSort(int low,int high){		//对记录序列R[s....t]进行快速排序
		if(low < high)   //长度大于1
		{	int pivotloc = Partition(low,high); //对R[s...t]进行一次划分，并返回枢轴位置  	    
	    QSort(low,pivotloc-1);				//对底端子序列递归排序
		QSort(pivotloc+1,high);				//对高断子序列递归排序
		}
	}
	void Quick(){ //快速排序
		for(int i=1; i<=AL; i++)
		{ Array2[i]=Array1[i]; } 
		QSort(1,AL);
		cout<<"\n经快速排序得:\n";
		for(i=1; i<=AL; i++)
		{	cout<<Array2[i]<<" ";	}
		cout<<"\n总共需要移动"<<N1<<"步"; N1=0;
		cout<<endl;
		getchar();
	} //-------------------Quick----------------

	void Heap(int s,int m){					// p282
	int Root = Array2[s];       //暂存根结点的记录
	for(int j = 2*s;j<=m;j*=2)  //沿KEY较大的孩子结点向下筛选
	{
		if(j<m&&Array2[j]<Array2[j+1])++j; //j为key较大孩子记录的下标
		if(Root>=Array2[j])break;        //不需要调整
		Array2[s] = Array2[j];   //把大于关键字记录往上调
		s = j;
		N2++;
	}
	Array2[s] = Root;     //回移筛选小来的记录
	}
	void Heapsort()
	{	for(int i=1; i<=AL; i++)
		{ Array2[i]=Array1[i]; } 
		int M;
		for(i = AL/2;i>0;--i)   //把H.r[1...AL]建成大顶堆
		{	Heap(i,AL);
			M = Array2[1];
			Array2[1] = Array2[AL];
			Array2[AL] = M;
			N2++;}
		//交换"堆顶"和"堆底"的记录
		for(i = AL-1;i>1;--i)
		{
			Heap(1,i);   //从根开始调整，将H.r[1....i]重新调整为大顶堆
			M = Array2[1];
			Array2[1] = Array2[i];
			Array2[i] = M; 
			N2++;
		//将堆顶记录和当前的"堆底"记录相互交换使已有序的记录堆移到底部
		}
		cout<<"\n经堆排序得:\n";
		for(i=1; i<=AL; i++)
		{	cout<<Array2[i]<<" ";	}
		cout<<"\n总共需要移动"<<N2<<"步";  N2=0;
		cout<<endl;
		getchar();
	}//------------------------Heapsort-----------------

	void ShellInsert(int dk){					//p271
	for(int i=dk+1;i<=AL;++i)
		if(Array2[i]<Array2[i-dk]){          //需将Array2.[i]插入有序增量子表
		  Array2[0]=Array2[i];				//暂存在Array2.[0]
		  int j=i-dk;
			do
			{	Array2[j+dk] = Array2[j];
				j = j - dk;
			}while(j > 0&&Array2[0] < Array2[j]);                 //记录后移，查找插入位置
			Array2[j+dk]=Array2[0];								//插入
			N3++;
			}
	}
	void Shell( ){
		for(int i=1; i<=AL; i++)
		{ Array2[i]=Array1[i]; }	
		int dlta=5;	 //按增量序列dlta[0....t-1]对顺序表L作希尔排序
   		do
		{	dlta = dlta/3+1;
			ShellInsert(dlta);
		}while(dlta > 1);
			cout<<"\n经堆排序得:\n";
			for(i=1; i<=AL; i++)
			{ cout<<Array2[i]<<" ";	}
			cout<<"\n总共需要移动"<<N3<<"步";  N3=0;
			cout<<endl;
			getchar();
	}//----------------------------Shell--------------------------
}A;

//***********产生随机数的函数*******************
void CreatRandomNum()
{
	int i, a;
	cout<<"\t注: 产生随机数不大于"<<Max<<".\n";
dd:	cout<<"\n输入要产生伪随机数的个数<'0'退出>: ";
	cin>>a;
	AL=a;
	if(a==0)
	{ cout<<"\n\tBYE...\n"; exit(0);}
	if(a>=1&&a<=Max)
	{	cout<<"\n  产生的随机数为:\n";
		for(i=1;i<=a;i++)
		{
		Array1[i]=(int)rand();// RandArray[i]=1+rand()%500000;
		cout<<Array1[i]<<" ";
		}
	 cout<<endl;
	}else
	{	cout<<"输入有误，重新输入!";
		goto dd;	}
}


//*****************界面函数*******************
void menue()
{
	cout<<endl<<endl;
	cout<<"  ********排序比较程序********";
	cout<<"\n\t1.   起泡法排序";
	cout<<"\n\t2.   直接插入法排序";
	cout<<"\n\t3.   简单选择排序";
	cout<<"\n\t4.   快速排序";
	cout<<"\n\t5.   希尔排序";
	cout<<"\n\t6.   堆排序";
	cout<<"\n\t7.   产生下一组随机数";
	cout<<"\n\t8.   退出程序....."; 
	cout<<"\n  *****************************\n";
}


//*****************主函数*********************
void main()
{	char c;
	menue();
dd:	CreatRandomNum();
	cout<<"\n按任意键继续..."<<endl;
	getchar();
	
	system("cls");
	while(1)
	{	menue();
		cout<<"\t请选择功能:";
		cin>>c;
		switch(c)
		{
			case '1':
					A.Bubble();
					system("cls"); break;
			case '2':
					A.StraightInsert();
					system("cls"); break;
			case '3':
					A.Select();
					system("cls"); break;
			case '4':
					A.Quick();
					system("cls"); break;
			case '5':
					A.Shell();
					system("cls"); break;
			case '6':
					A.Heapsort();
					system("cls"); break;
			case '7':
					goto dd;
					system("cls"); break;
			case '8':
				cout<<"\n\t程序结束...\n";
				exit(0); 
		}
	}
}