cintercmp.h

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

#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h> 
#include "stdafx.h"
#include <dos.h>
#include <conio.h>
#include <math.h>
#define MAXSIZE 1000 //排序表的最大容量
////////////////////////////////////////////////////////// 
////////////////////////////////////////////////////
//直接插入排序
class  CDirSort
{
public:
	int n;//要进行排序的随机数的个数
	int rand_data[10000];//最多可进行10000个数的比较
	int move_time;//移动的次数
	int cmp_time;//比较的次数
	void ReceiveData();
	void straipass1(int);
	void straisort();
	void DisplayOrginal();
	void DisplayNew();
	void BootFromFile();
	void SaveRandData();
	void Deal();
	void Deal1();
};

////////////////////////////////////////////////////////
void CDirSort::straipass1(int i)
{
	rand_data[0]=rand_data[i];//
	int j=i-1;
	int x=rand_data[i];
	cmp_time++;
	while(rand_data[j]>x)
	{
		cmp_time++;//比较的次数加1
		move_time++;//移动的次数加1
		rand_data[j+1]=rand_data[j];
		j--;
	}
	rand_data[j+1]=rand_data[0];
}

///////////////////////////////////////////////////////
void CDirSort::straisort()
{
	for(int i=2;i<=n;i++)
		straipass1(i);
}

//////////////////////////////////////////////////////

void CDirSort::ReceiveData()
{
	cout<<"请输入要排序的数的个数:";
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>rand_data[i];
}

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

/////////////////////////////////////////////////////
void CDirSort::DisplayNew()
{
	cout<<"排序后的序列是:\n";
	for(int i=1;i<=n;i++)
	{
		cout<<rand_data[i]<<" ";
		if(!(i%10))
			cout<<endl;
	}
	cout<<endl;
}

//////////////////////////////////////////
void CDirSort::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 CDirSort::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 CDirSort::Deal()
{
    //SaveRandData();
	BootFromFile();
	move_time=0;//初始化
	cmp_time=0;//初始化
	DisplayOrginal();
	straisort();
	DisplayNew();
	cout<<"移动的次数:"<<move_time<<endl;
	cout<<"比较的次数:"<<cmp_time<<endl;
}
///////////////////////////////////////////
void CDirSort::Deal1()
{
    //SaveRandData();
	BootFromFile();
	move_time=0;//初始化
	cmp_time=0;//初始化
	straisort();
}
//////////////////////////////////////////
//////////////////////////////////////////

//////////////////////////////////////////
//折半插入排序
class CBinSort
{
	public:
	int n;//要进行排序的随机数的个数
	int rand_data[10000];//最多可进行10000个数的比较
	int move_time;//移动的次数
	int cmp_time;//比较的次数
	void ReceiveData();
	void BinPass(int);
	void BinSort();
	void DisplayOrginal();
	void DisplayNew();
	void BootFromFile();
	void SaveRandData();
	void Deal();
	void Deal1();
};
//////////////////////////////////////////
void CBinSort::BinPass(int i)
{
	rand_data[0]=rand_data[i];//
	int s=1,j=i-1,m;
	int x=rand_data[i];
	while(s<=j)
	{
		m=(s+j)/2;
		if(x<rand_data[m])
			j=m-1;
		else
			s=m+1;
		cmp_time++;
	}
	for(int k=i-1;k>=j+1;k--)
	{
		rand_data[k+1]=rand_data[k];
		move_time++;
	}
	rand_data[j+1]=rand_data[0];
}
////////////////////////////////////////
void CBinSort::BinSort()
{
	for(int i=2;i<=n;i++)
		BinPass(i);
}
//////////////////////////////////////////
void CBinSort::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 CBinSort::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 CBinSort::DisplayOrginal()
{
	cout<<"原来的序列是:\n";
	for(int i=1;i<=n;i++)
	{
		cout<<rand_data[i]<<" ";
		if(!(i%10))
			cout<<endl;
	}
	cout<<endl;
}

/////////////////////////////////////////////////////
void CBinSort::DisplayNew()
{
	cout<<"排序后的序列是:\n";
	for(int i=1;i<=n;i++)
	{
		cout<<rand_data[i]<<" ";
		if(!(i%10))
			cout<<endl;
	}
	cout<<endl;
}
///////////////////////////////////////////
void CBinSort::Deal()
{
    //SaveRandData();
	BootFromFile();
	move_time=0;//初始化
	cmp_time=0;//初始化
	DisplayOrginal();
	BinSort();
	DisplayNew();
	cout<<"移动的次数:"<<move_time<<endl;
	cout<<"比较的次数:"<<cmp_time<<endl;
}
//////////////////////////////////////////
void CBinSort::Deal1()
{
    //SaveRandData();
	BootFromFile();
	move_time=0;//初始化
	cmp_time=0;//初始化
	BinSort();
}
//////////////////////////////////////////
//快速排序
class CQuickSort
{
	public:
	int n;//要进行排序的随机数的个数
	int k;
	int rand_data[10000];//最多可进行10000个数的比较
	int move_time;//移动的次数
	int cmp_time;//比较的次数
	void ReceiveData();
	void qkpass(int,int,int&);
	void qksort(int,int);
	void DisplayOrginal();
	void DisplayNew();
	void BootFromFile();
	void SaveRandData();
	void Deal();
	void Deal1();
};
//////////////////////////////////////////
void CQuickSort::qkpass(int s,int t,int& i)
{
	i=s;
	int j=t;
	int x=rand_data[s];
	while(i<j)
	{
		cmp_time++;
		while((i<j)&&(rand_data[j]>=x))
		{
			j--;
			cmp_time++;
		}
		rand_data[i]=rand_data[j];
		move_time++;
		cmp_time++;
		while((i<j)&&(rand_data[i]<=x))
		{
			i++;
			cmp_time++;
		}
		rand_data[j]=rand_data[i];
		move_time++;
	}
	rand_data[i]=x;
	move_time++;
}

////////////////////////////////////////
void CQuickSort::qksort(int s,int t)
{
	if(s<t)
	{
		qkpass(s,t,k);
		qksort(s,k-1);
		qksort(k+1,t);
	}
}
//////////////////////////////////////////
void CQuickSort::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 CQuickSort::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 CQuickSort::DisplayOrginal()
{
	cout<<"原来的序列是:\n";
	for(int i=1;i<=n;i++)
	{
		cout<<rand_data[i]<<" ";
		if(!(i%10))
			cout<<endl;
	}
	cout<<endl;
}

/////////////////////////////////////////////////////
void CQuickSort::DisplayNew()
{
	cout<<"排序后的序列是:\n";
	for(int i=1;i<=n;i++)
	{
		cout<<rand_data[i]<<" ";
		if(!(i%10))
			cout<<endl;
	}
	cout<<endl;
}
///////////////////////////////////////////
void CQuickSort::Deal()
{
    //SaveRandData();
	BootFromFile();
	move_time=0;//初始化
	cmp_time=0;//初始化
	DisplayOrginal();
	qksort(1,n);
	DisplayNew();
	cout<<"移动的次数:"<<move_time<<endl;
	cout<<"比较的次数:"<<cmp_time<<endl;
}
///////////////////////////////////////////
void CQuickSort::Deal1()
{
    //SaveRandData();
	BootFromFile();
	move_time=0;//初始化
	cmp_time=0;//初始化
	qksort(1,n);
}
//////////////////////////////////////////
//////////////////////////////////////////
//简单选择排序
class CSimpSecSort
{
	public:
	int n;//要进行排序的随机数的个数
	int k;
	int rand_data[10000];//最多可进行10000个数的比较
	int move_time;//移动的次数
	int cmp_time;//比较的次数
	void ReceiveData();
	void smp_selecpass(int);
	void smp_selecsort();
	void DisplayOrginal();
	void DisplayNew();
	void BootFromFile();
	void SaveRandData();
	void Deal();
	void Deal1();
};
//////////////////////////////////////////
void CSimpSecSort::smp_selecpass(int i)
{
	k=i;
	for(int j=i+1;j<=n;j++)
	{
		cmp_time++;
	    if(rand_data[j]<rand_data[k])
			k=j;
	}
	if(k!=i)
	{
		move_time+=3;
		int tem=rand_data[i];
		rand_data[i]=rand_data[k];
		rand_data[k]=tem;
	}

}

////////////////////////////////////////
void CSimpSecSort::smp_selecsort()
{
	for(int i=1;i<=n-1;i++)
		smp_selecpass(i);
}
//////////////////////////////////////////
void CSimpSecSort::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 CSimpSecSort::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 CSimpSecSort::DisplayOrginal()
{
	cout<<"原来的序列是:\n";
	for(int i=1;i<=n;i++)
	{
		cout<<rand_data[i]<<" ";
		if(!(i%10))
			cout<<endl;
	}
	cout<<endl;
}

/////////////////////////////////////////////////////
void CSimpSecSort::DisplayNew()
{
	cout<<"排序后的序列是:\n";
	for(int i=1;i<=n;i++)
	{
		cout<<rand_data[i]<<" ";
		if(!(i%10))
			cout<<endl;
	}
	cout<<endl;
}
///////////////////////////////////////////
void CSimpSecSort::Deal()
{
    //SaveRandData();
	BootFromFile();
	move_time=0;//初始化
	cmp_time=0;//初始化
	DisplayOrginal();
	smp_selecsort();
	DisplayNew();
	cout<<"移动的次数:"<<move_time<<endl;
	cout<<"比较的次数:"<<cmp_time<<endl;
}
///////////////////////////////////////////
void CSimpSecSort::Deal1()
{
    //SaveRandData();
	BootFromFile();
	move_time=0;//初始化
	cmp_time=0;//初始化
	smp_selecsort();
}
	
//////////////////////////////////////////
	
//////////////////////////////////////////
//堆排序
class CHeapSort
{
	public:
	int n;//要进行排序的随机数的个数
	int rand_data[10000];//最多可进行10000个数的比较
	int move_time;//移动的次数
	int cmp_time;//比较的次数
	void ReceiveData();
	void shif(int,int);
	void heapsort();
	void DisplayOrginal();
	void DisplayNew();
	void BootFromFile();
	void SaveRandData();
	void Deal();
	void Deal1();
};
//////////////////////////////////////////
void CHeapSort::shif(int k,int m)
{
    int i=k,j=2*i;
	int x=rand_data[k];
	bool finished=false;
	int t=rand_data[k];
	while((j<=m)&&(!finished))
	{
		cmp_time++;
		if((j<m)&&(rand_data[j]>rand_data[j+1]))
			j++;
		cmp_time++;
		if(x<=rand_data[j])
			finished=true;
		else
		{
			move_time++;
			rand_data[i]=rand_data[j];
			i=j;
			j=2*i;
		}
	}
	rand_data[i]=t;
	move_time++;
}

////////////////////////////////////////
void CHeapSort::heapsort()
{
	for(int i=n/2;i>=1;i--)
		shif(i,n);
	for(i=n;i>=2;i--)
	{
		int tem;
		tem=rand_data[i];
		rand_data[i]=rand_data[1];
		rand_data[1]=tem;
		move_time+=3;
		shif(1,i-1);
	}
}
//////////////////////////////////////////
void CHeapSort::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 CHeapSort::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 CHeapSort::DisplayOrginal()
{
	cout<<"原来的序列是:\n";
	for(int i=1;i<=n;i++)
	{
		cout<<rand_data[i]<<" ";
		if(!(i%10))
			cout<<endl;
	}
	cout<<endl;
}

/////////////////////////////////////////////////////
void CHeapSort::DisplayNew()
{
	cout<<"排序后的序列是:\n";
	for(int i=1;i<=n;i++)
	{
		cout<<rand_data[i]<<" ";
		if(!(i%10))
			cout<<endl;
	}
	cout<<endl;
}
///////////////////////////////////////////
void CHeapSort::Deal()
{
    //SaveRandData();
	BootFromFile();
	move_time=0;//初始化
	cmp_time=0;//初始化
	DisplayOrginal();
	heapsort();
	DisplayNew();
	cout<<"移动的次数:"<<move_time<<endl;
	cout<<"比较的次数:"<<cmp_time<<endl;
}
///////////////////////////////////////////
void CHeapSort::Deal1()
{
    //SaveRandData();
	BootFromFile();
	move_time=0;//初始化
	cmp_time=0;//初始化
	heapsort();
}
//////////////////////////////////////////
//////////////////////////////////////////
//起泡排序
class CBubbleSort
{
	public:
	int n;//要进行排序的随机数的个数
	bool flag;
	int rand_data[10000];//最多可进行10000个数的比较
	int move_time;//移动的次数
	int cmp_time;//比较的次数
	void ReceiveData();
	void bubblepass(int);
	void bubblesort();
	void DisplayOrginal();
	void DisplayNew();
	void BootFromFile();
	void SaveRandData();
	void Deal();
	void Deal1();
};
//////////////////////////////////////////