sort.cpp

题 目: 堆排序、直接插入排序算法比较 初始条件： 试通过随机数据比较堆排序、直接插入排序算法的关键字比较次数和关键字移动次数。 （1）待排序表的表长不小于100；其中的数据要用伪随机数产生

#include<stdio.h>
#include<stdlib.h>
#include<iostream> 
using namespace std;
#define MAXSIZE 1000  //可排序的表的最大长度
void HeapSort(long&c,long&s);
void InsertSort(long&c,long&s);
void BeforeSort();
void Shift(int i,int j);
void Swap(int i,int j);
void InitList(int n);
typedef int DataType[MAXSIZE+2];//Data[-1]和Data[MAXSIZE+1]为辅助单元
DataType data;                  //可排序表的顺序存储空间
DataType data2;                 //辅助空间，保留最新打乱的数据
int size;                       // 表的当前长度
long compCount;                 //关键字的比较次数
long shiftCount;                //关键字的移动次数
void BeforeSort(){//格式化
	 compCount=shiftCount=0;
}
bool Less(int i,int j){
	//若表中第i个元素小于第j个元素，则返回ture,否则返回false
	compCount++;//关键字比较次数加1
	return data[i]<data[j];
}
void Swap(int i,int j){
	//交换表中第i和第j个数据元素
	int temp;
	temp=data[i];
	data[i]=data[j];
	data[j]=temp;
	shiftCount=shiftCount+3;//关键字比较次数加3
}
void Shift(int i,int j){
	//将表中第i个元素的值赋给第j个元素
	data[j]=data[i];
	shiftCount++;//关键字移动次数加1
}
void CopyData(DataType list1,DataType list2){//复制数据
	int i;
	for(i=1;i<=size;i++)data2[i]=data[i];
}

void InitList(int n,DataType data){
	int i;
      for( i = 0; i < n;i++ ) 
	  { data[i]=rand();
	  CopyData(data2,data);
	  }
      compCount=shiftCount=0;
	  size=n;
}
void InsertSort(long&c,long&s){
	//进行直接插入排序，返回关键字比较次数c和移动次数s
	int i,j;
	BeforeSort();
	for(i=2;i<=size;i++){
		Shift(i,0);j=i-1;
		while(Less(0,j)){Shift(j,j+1);j--;}
		Shift(0,j+1);
	}
	c=compCount;s=shiftCount;
}
void Sift(int left,int right){//堆排序的调堆函数
	int i,j;
	bool finished;
	i=left;j=2*i;Shift(left,0);finished=false;
	while(j<=right&&!finished){
		if(j<right&&Less(j+1,j))j=j+1;
		if(!Less(j,0))finished=true;
		else{Shift(j,i);i=j,j=2*i;}
	}
	Shift(0,i);
}
void HeapSort(long&c,long&s){
	//进行堆排序，返回关键字比较次数c和移动次数s
	int left,right;
	BeforeSort();
	for(left=size/2;left>=1;left--)Sift(left,size);
	for(right=size;right>=2;right--)
	{Swap(1,right);Sift(1,right-1);}
	c=compCount;s=shiftCount;
}
void main(){
   int i,j;
	for(i=1;i<=5;i++){
	     long c,s;
         int n;
		 cout<<"请输入待排序表的表长(不小于100，不大于1000)"<<endl;
		 cin>>n;
		  if(n<100||n>1000)cout<<"您的输入不符合要求"<<endl;
		  else
		  {
	        cout<<"待排序表的表长为"<<n<<endl;
	        InitList(n, data);
			
			cout<<"直接插入排序："<<endl;
	           InsertSort(c,s);
			   cout<<"关键字比较次数:"<<" "<<c<<"关键字移动次数:"<<" "<<s<<endl;
			   InitList(n, data);
			   cout<<"堆排序:"<<endl;
	           HeapSort(c,s);
			   cout<<"关键字比较次数:"<<" "<<c<<"关键字移动次数:"<<" "<<s<<endl;
		  }
		
		 
	}
}