内部排序比较.cpp

各种排序方法的比较。有冒泡法

//************************************算法比较*********************************

/*
	要求：利用随机函数产生N个随机整数（N = 500，1000，1500，2000，2500，…,30000），
利用直接插入排序、折半插入排序，起泡排序、快速排序、希尔排序、选择排序、归并排序、堆排序、
基数排序九种排序方法（可添加其它排序方法）进行排序（结果为由小到大的顺序），并统计每一种
排序所耗费的时间（统计为图表坐标形式）。

*/

//******************************************************************************

#include<iostream.h>	
#include<string.h>
#include<fstream.h>
#include <stdlib.h>
#include<time.h>
#include<iomanip.h>
#include<stdio.h>



#define maxSize 5000
//********************************************************************
//静态链表的建立
#define maxKeyNum 5
#define radix 10
#define maxSpace maxSize+1

typedef struct
{
	int keys[maxKeyNum];
	int elem;
	int next;
}SlCell;

typedef struct
{
	SlCell r[maxSpace];
	int keynum;
	int length;
}SlList;
typedef int arrayPtr[radix];

//********************************************************************
//线性表的建立

typedef  struct  
{
	int  * elem;					//存储空间基址
	
	int  length ;					//线性表当前长度
	
	int  listsize;					//线性表分配的总长度

}sqlist;


//******************************************************************************
//*************************		  函数声明        ******************************
//******************************************************************************
//线性表函数声明
int compare(int a,int b);//比较函数
int emptylist(sqlist l);//判空函数
int clearlist(sqlist &l);//清空线性表函数
int initlist(sqlist &l,int size);//建空表函数
void  newlist(sqlist &l,int n);//建非空表函数
int   destroysqlist(sqlist &l);//销毁线性表
int locateelem(sqlist l, int value);//定位函数
int  listinsert( sqlist &l, int i, int e);//插入函数
int deletelist(sqlist &l, int i ,int &e);//删除元素函数
sqlist  realloc(sqlist, int,int);//自定义realloc函数

//赋值函数声明
void FindKey(SlList &l,int j);//对静态链表赋关关键值
void GetRandWorth(sqlist &l,int sum);//生成随机数,并赋给线性表的关键码
void GetRadixWorth(SlList &l,int sum);//生成随机数,并赋给静态链表的elem
void Filelist(char filename[]);//用文件存储随机数函数
void Newsllist(SlList &list,char filename[],int sum);//用文件随机函数创建静态链表
void Newsqlist(sqlist &l,char filename[],int sum);//用文件随机函数创建线性表

//文件存储函数声明
void saveStyleSum(char filename[],int sum);
void saveStyleHead(char filename[]);
void saveResult(int t1,int t2,int i,char filename[]);

//排序算法函数声明

//冒泡排序
void BubbleSort(sqlist &l);
//直接插入排序
void InsertSort(sqlist &l);
//折半插入排序
void BInsertSort(sqlist &l);
//希尔排序
void ShellInsert(sqlist &l,int dk);
void ShellSort(sqlist &l);
//快速排序
int Partition(sqlist &l,int low,int high);
void QSort(sqlist &l,int low,int high);
//选择排序
void SelectSort(sqlist &l);
//堆排序
typedef sqlist HeapType;
void HeapAdjust(HeapType &h,int s,int m);
void HeapSort(HeapType &h);
//归并排序
void merge(sqlist sr,sqlist &tr,int l,int m,int n);
void MSort(sqlist sr,sqlist &tr1,int s,int t);
void MergeSort(sqlist &l);
//基数排序
void Distribute(SlList &l,int i,arrayPtr &f,arrayPtr &e);
void Collect(SlList &l,int i,arrayPtr f,arrayPtr e);
void RadixSort(SlList &l);

//******************************************************************************
//**************************       主函数         ******************************
//******************************************************************************
void main(void)
{
	sqlist list;
	SlList sllist;
	int i;
	
	fstream listfile;			//刷新文件
	listfile.open("result.txt",ios::out);
	
	if(listfile.fail())
	{
		cout<<"文件打开失败!"<<endl;
		exit(0);
	}
	listfile.close();

	
	int t1,t2,t3,t4,t5,t6,t7,t8,t9,t10,t11,t12,t13,t14,t15,t16,t17,t18;
	
	initlist(list,maxSize);
	Filelist("data.txt");

	cout<<setw(6)<<"数目"<<setw(8)<<"冒泡"<<setw(10)<<"直接插入"<<setw(10)<<"折半插入";
	cout<<setw(6)<<"希尔"<<setw(8)<<"快速"<<setw(7)<<"选择"<<setw(5)<<"堆";
	cout<<setw(10)<<"归并"<<setw(8)<<"基数"<<endl;
	
	saveStyleHead("result.txt");//文件存储
	for(int sum=500;sum<=5000;sum+=500)
	{
		i=1;
		saveStyleSum("result.txt",sum);//文件存储格式
		
		//冒泡排序
		Newsqlist(list,"data.txt",sum);
		t1=clock( );
        BubbleSort(list);  
        t2=clock( );
		saveResult(t1,t2,i,"result.txt");
		i++;


		//直接插入排序
		Newsqlist(list,"data.txt",sum);
		t3=clock( );
        InsertSort(list);
        t4=clock( );
		saveResult(t3,t4,i,"result.txt");
		i++;


		//折半插入排序
		Newsqlist(list,"data.txt",sum);
		t5=clock( );
        BInsertSort(list); 
        t6=clock( );
		saveResult(t5,t6,i,"result.txt");
		i++;


		//希尔排序
		Newsqlist(list,"data.txt",sum);
		t7=clock( );
        ShellSort(list);   
        t8=clock( );
		saveResult(t7,t8,i,"result.txt");
		i++;


		//快速排序
		Newsqlist(list,"data.txt",sum);
		t9=clock( );
        QSort(list,1,list.length);
        t10=clock( );
		saveResult(t9,t10,i,"result.txt");
		i++;


		//选择排序
		Newsqlist(list,"data.txt",sum);
		t11=clock( );
        SelectSort(list);   
        t12=clock( );
		saveResult(t11,t12,i,"result.txt");
		i++;


		//堆排序
		Newsqlist(list,"data.txt",sum);
		t13=clock( );
        HeapSort(list);    
        t14=clock( );
		saveResult(t13,t14,i,"result.txt");
		i++;

		//归并排序
		Newsqlist(list,"data.txt",sum);
		t15=clock( );
	    MergeSort(list);    
        t16=clock( );
		saveResult(t15,t16,i,"result.txt");
		i++;

		
		//基数排序
		Newsllist(sllist,"data.txt",sum);
		t17=clock( );
        RadixSort(sllist);
        t18=clock( );
		saveResult(t17,t18,i,"result.txt");
		i++;
		
		cout<<setw(5)<<sum<<setw(8)<<(t2-t1)<<setw(7)<<(t4-t3)<<setw(10)<<(t6-t5);
		cout<<setw(8)<<(t8-t7)<<setw(8)<<(t10-t9)<<setw(7)<<(t12-t11)<<setw(6)<<(t14-t13);
		cout<<setw(10)<<(t16-t15)<<setw(8)<<(t18-t17)<<endl;;
	   
	}
}


//********************************************************************
//建空表函数
//用户输入空表空间size

int initlist(sqlist &l,int size)
{  
    l.elem =new int[size+1];

    if(!l.elem)					//存储分配失败
	  exit(0);
  
    l.length=0;
    l.listsize=size;
 
    return 1;
}
//清空线性表函数
   
int clearlist(sqlist &l)

{  
      l.length=0;
	  
	  return 1;
}

//********************************************************************
//销毁线性表

int   destroysqlist(sqlist &l)
{
	 delete(l.elem);
	 
	 l.elem=NULL;
	 l.length=0;
	 l.listsize=0;
	 
	 return 1;
 }     

//********************************************************************
//判空函数

int emptylist(sqlist l)
{
	if(l.length!=0)
		return 1;
	
	else 
		return 0;
}


//********************************************************************
//定位函数
      
//自定义compare函数

int compare(int a,int b)
{
	 if(a==b)
		  return 1;	 
	 else 
		 return 0;
}


//定位函数

int locateelem(sqlist l, int value)
{
	  int i;
	  
      if(l.length==0)				//对空表作事先判断
	  {
		  cout<<"此表为空！"<<endl;
	      exit(0);
	  }
	  	
	  for(i=1;i<=l.length;i++)//定位
	  {
		  if (compare(value,l.elem[i])!=0)	  
			break;
	  }
	  if((i>0)&&i<=(l.length))
		  return i;
	  else							//对表中无此结点的判断
	  { 
		  cout<<"表中无此数！"<<endl;
	      return 0;
	  }
}

//********************************************************************
//插入函数


//自定义realloc函数 

//功能：当前线性表分配的总存储空间已满时，增加分配

//设当前线性表最大存储空间为size

sqlist  realloc(sqlist l, int size,int extra=1)
{
      sqlist present; 
	  int i;
	   
	  present.elem=new int[size+extra];
	  
	  if(!present.elem)//存储分配申请失败
		  exit(0);

      for(i=1;i<=size;i++)//把原线性表数据转移至新表
	  {
		 present.elem[i]=l.elem[i];
	  }
      
	  present.listsize=size+extra;
      present.length=size;
		 
	  return present;	

}


//插入函数
  
int  listinsert( sqlist &l, int i, int e)
{	  
      if (i<1||i>(l.length))//对输入位置的有效性判断
	  { 
		  cout<<"该位置无效！"<<endl;
	      return 0;
	  }
	  
	  if(l.length==l.listsize)//表满，增加存储空间
	  { 
		  cout<<"表满"<<endl;
		  
		  clearlist(l);//清空l
	      
		  l=realloc(l,l.listsize);//自定义realloc函数 
	  }

	  int position;
	  
	  for(position=l.length+1;position>i;position--)
		  l.elem[position]=l.elem[position-1];
	 
	  l.elem[i]=e;
	  l.length++;
	  
	  return 1;

}

//********************************************************************
//删除元素函数

int deletelist(sqlist &l, int i ,int &e)
{
	  int position;
      
	  if((i<1)||(i>l.length))			//对输入位置的有效性判断
	  {
		  cout<<"该位置无效！"<<endl;
		  return 0;
	  }
  
	  e=l.elem[i];

	  for (position=i;position<l.length;position++)//删除并移动元素
	  {  
		  l.elem[position]=l.elem[position+1];
	  }
	  
	  l.length--;
	  	  
	  return e;

}

//********************************************************************
//对静态链表赋关关键值

void FindKey(SlList &l,int j)
{

    l.r[j].keys[4]=l.r[j].elem/10000;
	l.r[j].keys[3]=l.r[j].elem%10000/1000;
	l.r[j].keys[2]=l.r[j].elem%1000/100;
	l.r[j].keys[1]=l.r[j].elem%100/10;
	l.r[j].keys[0]=l.r[j].elem%10;
}

//********************************************************************
//生成随机数,并赋给线性表的关键码

void GetRandWorth(sqlist &l,int sum)
{
	int j;
    srand( (unsigned)time( NULL ) );
    for( j=1;j<=sum;j++ )
    {
			l.elem[j]=rand( ) % 32767- rand( ) % 32767;
			if(l.elem[j]<0)
				l.elem[j]=-l.elem[j];
		l.length++;
    }	
}

//********************************************************************
//生成随机数,并赋给静态链表的elem

void GetRadixWorth(SlList &l,int sum)
{
	int j;
 	l.length=0;
	l.keynum=5;
    for( j=1;j<=sum;j++ )
    {
           
			l.r[j].elem=rand( ) % 32767- rand( ) % 32767;
			if(l.r[j].elem<0)
				l.r[j].elem=-l.r[j].elem;
     
		   FindKey(l,j);
           l.length++;
	}
}