a.cpp

用四种方法实现对随机的10000个数的排序

#include<iostream.h>
#include<stdlib.h>
#include<iomanip.h>
#include<fstream.h>
typedef int ElemType;
int com=0,mov=0;
//对数组A中的n个元素进行直接插入排序
void InsertSort(ElemType A[],int n)
{
	ElemType x;
	int i,j;
	for(i=1;i<n;i++){                  //i表示插入次数，共进行n-1次插入
		x=A[i];                        //暂存待插入有序表中的元素A[i]
		for(j=i-1;j>=0;j--){
			com++;
			if(x<A[j]) {
				A[j+1]=A[j];     //进行顺序比较和移动
				mov++;
			}
			else break;                 //查询到j+1位置时离开j循环
		}
			A[j+1]=x;                   //把原A[i]的值插入到下标为j+1的位置
	}

}



//采用快速排序方法对数组A中A[s]～A[t]区间进行排序
//开始进行递归调用时s和t的处置应该分别为0和n-1
void QuickSort(ElemType A[],int s,int t)
{
	//对当前排序区间进行一次划分
	int i=s+1,j=t;            //给i和j赋初值
	ElemType x=A[s];          //把枢轴的值暂存在x中
	while(i<=j){
		while(A[i]<=x&&i<=j) {i++;com++;}                    //从前向后顺序比较
		while(A[j]>=x&&j>=i) {j--;com++;}                    //从后向前顺序比较
		if(i<j){                                     //当条件成立时交换A[i]和A[j]的值
			ElemType temp=A[i];A[i]=A[j];A[j]=temp;mov++;
			i++;j--;
		}
	}
	//交换A[s]和A[j]的值，得到前后两个子区间A[s]～A[j-1]和A[j+1]～A[t]
	if(s!=j){A[s]=A[j];A[j]=x;mov++;}
	//在当前左区间内超过一个元素的情况下递归处理左区间
	if(s<j-1)QuickSort(A,s,j-1);
	//在当前右区间内超过一个元素的情况下递归处理右区间
	if(j+1<t)QuickSort(A,j+1,t);
}



//把A数组中两个相邻的有序表A[s]～A[m]和A[m+1]～A[t]
//归并为R数组中对应位置上的一个有序表R[s]～R[t]
void TwoMerge(ElemType A[],ElemType R[],int s,int m,int t)
{
	int i,j,k;
	i=s;j=m+1;k=s;         //分别给只是每个有序表元素位置的指针赋初值
	//两个有序表中同时存在未归并元素时的处理过程
	while(i<=m&&j<=t){
		com++;
		if(A[i]<=A[j]){
			R[k]=A[i];i++;k++;mov++;
		}
		else{
			R[k]=A[j];j++;k++;mov++;
		}
	}
	//对第一个有序表中存在的为归并元素进行处理
	while(i<=m){
		R[k]=A[i];i++;k++;mov++;
	}
	//对第二个有序表中存在的为归并元素进行处理
	while(j<=t){
		R[k]=A[j];j++;k++;mov++;
	}
}
//把数组A[n]中每个长度为len的有序表两两归并到数组R[n]中
void MergePass(ElemType A[],ElemType R[],int n,int len)
{
	int p=0;                                //p为每一个待各并表的第一个元素的下标，初值为0
	//两两归并长度均为len的有序表
	while(p+2*len-1<=n-1){
		TwoMerge(A,R,p,p+len-1,p+2*len-1);
		p+=2*len;
	}
	if(p+len-1<n-1)                         //归并最后两个长度不等的有序表
		TwoMerge(A,R,p,p+len-1,n-1);
	else
		for(int i=p;i<=n-1;i++)
			R[i]=A[i];                      //把剩下的最后一个有序表复制到R中
}
//采用归并排序的方法对数组A中的n个记录进行排序
void MergeSort(ElemType A[],int n)
{
	ElemType*R=new ElemType[n];          //定义长度为n的辅助数组R
	int len=1;                           //从有序表长度为1开始
	while(len<n){
		//从A归并到R中，得到每个有序表的长度为2*len
		MergePass(A,R,n,len);
		//修改len的值为R中的每个有序表的长度
		len*=2;
		//从R归并到A中，得到每个有序表的长度为2*len
		MergePass(R,A,n,len);
		//修改len的值为A中的每个有序表的长度
		len*=2;
	}
	delete[]R;               //释放R数组所占用的动态存储空间
}

//对A[n]数组中的A[i]元素进行筛选运算，形成以A[i]为根的堆
void Sift(ElemType A[],int n,int i)
{
	ElemType x=A[i];              //把待筛结点存入x中
	int j;
	j=2*i+1;                      //A[j]是A[i]的左孩子
	while(j<=n-1){                //当A[i]的左孩子不为空时执行循环
		com++;
		//若右孩子的排序码较大，则把j修改为右孩子的下标
		if(j<n-1&&A[j]<A[j+1]) j++;
		//将A[j]调到双亲位置上，修改i和j的值，以便继续向下筛选
		if(x<A[j]){
			A[i]=A[j];i=j;j=2*i+1;mov++;
		}                             //找到x的最终位置，终止循环
		else break;
	}
	A[i]=x;                           //被筛结点放入最终位置
}
//利用堆排序的方法对数组A中的n个元素进行排序
void HeapSort(ElemType A[],int n)
{
	ElemType x;
	int i;
	for(i=n/2-1;i>=0;i--) Sift(A,n,i);            //建立初始堆
	for(i=1;i<=n-1;i++){                          //进行n-1次循环，完成堆排序
		//将树根节点的值同当前区间内最后一个结点的值对换
		x=A[0];A[0]=A[n-i];A[n-i]=x;mov++;
		//筛A[0]结点，得到n-i个结点的堆
		Sift(A,n-i,0);
	}
}
void main(){
	const int N=10000;
    int m,k,seed=5641;
	cout<<"请选择排序方式："<<endl;
	cout<<'\t'<<"1.插入排序"<<endl;
	cout<<'\t'<<"2.快速排序"<<endl;
	cout<<'\t'<<"3.归并排序"<<endl;
	cout<<'\t'<<"4.堆排序"<<endl;
	cin>>k;
	int C[N];
	srand(seed);
	ofstream output("outputfile.txt",ios::ate);
	output<<"////////////////////////////////////////"<<endl;
	output<<"/////////随机生成的待排序数组为/////////"<<endl;
	output<<"////////////////////////////////////////"<<endl;
	for(m=0;m<N;m++){
		C[m]=rand();	
		output<<setw(6)<<C[m];
		if((m+1)%12==0)
			output<<endl;
	}
	int a=0,b=0,c=0,d=0,e=0,f=0,j=0;
	for(m=0;m<N;m++){
		if(C[m]<4681) a++;
		else if(C[m]<9362) b++;
			else if(C[m]<14043) c++;
                else if(C[m]<18724) d++;
					else if(C[m]<23405) e++;
						else if(C[m]<28086) f++;
						/*	else if(C[m]<21000) g++;
								else if(C[m]<24000) h++;
									else if(C[m]<27000) i++;*/
									     else j++;
	/*	if(C[m]<15000)a++;
		else if(C[m]<20000)b++;
		     else c++;*/
	}
	cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<e<<" "<<f<<" "<<j<<endl;




	output<<endl;
	switch(k){
	case 1:
		
		output<<"////////////////////////////////////////"<<endl;
		output<<"//////////////插入排序结果//////////////"<<endl;
		output<<"////////////////////////////////////////"<<endl;
		InsertSort(C,N);
		break;
	case 2:
	
		output<<"////////////////////////////////////////"<<endl;
		output<<"//////////////快速排序结果//////////////"<<endl;
		output<<"////////////////////////////////////////"<<endl;
		QuickSort(C,0,N-1);
		break;
	case 3:
	
		output<<"////////////////////////////////////////"<<endl;
		output<<"//////////////归并排序结果//////////////"<<endl;
		output<<"////////////////////////////////////////"<<endl;
		MergeSort(C,N);
		break;
	case 4:
	
		output<<"////////////////////////////////////////"<<endl;
		output<<"///////////////堆排序结果///////////////"<<endl;
		output<<"////////////////////////////////////////"<<endl;
		HeapSort(C,N);
		break;
	}
		
	for(m=0;m<N;m++){
		output<<setw(6)<<C[m];
		if((m+1)%12==0)
			output<<endl;
	}
	
	output.close();
	cout<<"比较次数"<<com<<"  移动次数"<<mov<<endl;
	cout<<"欢迎使用，结果请见outputfile.txt文件，再见！";
	cout<<endl;
	
}