📄 sortanalysis_.cpp

📁 7中排序算法的比较代码
💻 CPP
字号:
#include<iostream>
#include "time.h"
#include<stdio.h>
#include<stdlib.h>
#define OVERFLOW -2
#define ERROR -1
#include<conio.h>
#define OK 1
#define MAXSIZE 500
#define LISTINCREMENT 1
using namespace std;
typedef int KeyType;
typedef struct 
{
	KeyType key;
}RedType;
typedef struct
{
	RedType r[MAXSIZE+1];
	int length;
}SqList;
//直接插入排序
int LT(int a,int b)
{
	if(a<b)
		return OK;
	else
		return ERROR;
}

void InsertSort(SqList &L,long &c,long &d)//C为比较的次数，d为交换的次数
{
	for(int i=2;i<=L.length;++i)
	{
		if(LT(L.r[i].key,L.r[i-1].key)==OK)
		{
			
			 L.r[0]=L.r[i];
			 L.r[i]=L.r[i-1];
			 for(int j=i-2;LT(L.r[0].key,L.r[j].key)==OK;j--)
			 {
				 c++;d++;
				 L.r[j+1]=L.r[j];
			 }
			 L.r[j+1]=L.r[0];
		}
		c++;
	}
}
//简单选择排序
int SelectMinKey(SqList &L,int j,long &c,long &d)//C为比较的次数，d为交换的次数
{
	int minKey=j;
	L.r[0]=L.r[j];
	for(j++;j<=L.length;j++)
	{
		c++;
		if(L.r[j].key<L.r[0].key)
		{
         L.r[0]=L.r[j];
		 minKey=j;
		}
	} 
	return minKey;
}
void SelectSort(SqList &L,long &c,long &d)//C为比较的次数，d为交换的次数
{
	int j;
	for(int i=1;i<L.length;i++)
	{
		j=SelectMinKey(L,i,c,d);
        if(i!=j)
		{
			L.r[0]=L.r[i];
			L.r[i]=L.r[j];
			L.r[j]=L.r[0];
			d++;
		}
	
	}
}
//快速排序
int Partition(SqList &L,int low, int high,long &c,long &d)//C为比较的次数，d为交换的次数
{
	L.r[0]=L.r[low];
	 int pivotkey=L.r[low].key;
	 while(low<high	)
	 {
          while(low<high&&L.r[high].key>=pivotkey)
		  {
			  --high; 
			  c++;
		  }
		  L.r[low]=L.r[high];
		  while(low<high&&L.r[low].key<=pivotkey)
		  { 
			  ++low;
			  c++;
		  }
		  L.r[high]=L.r[low];d++;
	 }
	 L.r[low]=L.r[0];d++;
	 return low;
}
void QSort (SqList &L,int low,int high,long &c,long &d)//C为比较的次数，d为交换的次数
{
    int pivotloc;
	if(low<high)
	{
		 pivotloc=Partition(L,low,high,c,d);
		 QSort(L,low,pivotloc-1,c,d);
		 QSort(L,pivotloc+1,high,c,d);
	}
}
//堆排


void HeapAdjust(SqList &H,int s,int m,long &c,long &d)//C为比较的次数，d为交换的次数
{
	H.r[0]=H.r[s];
	for(int j=2*s;j<=m;j*=2)
	{
		if(j<m&&LT(H.r[j].key,H.r[j+1].key)==OK)
			j++;c++;
		if(LT(H.r[0].key,H.r[j].key)==ERROR)
		{
			c++;
			break;
		}
		H.r[s]=H.r[j];d++;
		s=j;
	}
	H.r[s]=H.r[0];
}
void HeapSort(SqList &H,long &c,long &d)//C为比较的次数，d为交换的次数
{
	for(int i=H.length/2;i>0;i--)
		HeapAdjust(H,i,H.length,c,d);
	for(i=H.length;i>1;i--)
	{
		H.r[0]=H.r[i];
		H.r[i]=H.r[1];
		H.r[1]=H.r[0];d++;
		HeapAdjust(H,1,i-1,c,d);
	}
}
//归并排序
void Merge(SqList &TR,SqList &SR,int i,int m,int n,long &c,long &d)//C为比较的次数，d为交换的次数
{
	int j,k;
	for(j=m+1,k=i;i<=m&&j<=n;k++)
	{
        c++;
		if(LT(TR.r[i].key,TR.r[j].key)==OK)
		{
			SR.r[k]=TR.r[i++];
			d++;
		}
		else 
		{
			SR.r[k]=TR.r[j++];
			d++;
		}
	}
	while(i<=m)
	{
		SR.r[k++]=TR.r[i++];
		d++;
	}
     while(j<=n)
	 {
		SR.r[k++]=TR.r[j++];
		d++;
	}
	 TR=SR;
}
void MSort(SqList &SR,SqList &TR1,int s,int t,long &c,long &d)
{
	int m;
	if(s==t)
	{
		TR1.r[s]=SR.r[s];
		d++;
}
	else
	{
		m=(s+t)/2;
		MSort(SR,TR1,s,m,c,d);
		MSort(SR,TR1,m+1,t,c,d);
		Merge(TR1,SR,s,m,t,c,d);
	}
}
void MergeSort (SqList &L,SqList &T,long &c,long &d)
{
	MSort(L,T,1,L.length,c,d);
}
//希尔排序
void ShellInsert(SqList &L,int dk,long &c,long &d)//C为比较的次数，d为交换的次数
{
	int i,j;
	for(i=dk+1;i<=L.length;i++)
	{
		c++;
		if(LT(L.r[i].key,L.r[i-dk].key)==OK)
		{
			 L.r[0]=L.r[i];
			for(j=i-dk;j>0&&LT(L.r[0].key,L.r[j].key)==OK;j-=dk)
				 L.r[j+dk]=L.r[j];
			 L.r[j+dk]=L.r[0];d++;
		}
	}
}

void ShellSort(SqList &L, int dlta[],int t,long &c,long &d)
{
     for(int k=0;k<t;k++)
		 ShellInsert(L,dlta[k],c,d);
}
//折半插入排序
void BInsertSort(SqList &L,long &c,long &d)//C为比较的次数，d为交换的次数
{
	int i,j,low,high,m;
	long e=0;
	for(i=2;i<=L.length;++i)
	{
       L.r[0]=L.r[i];
       low=1; high=i-1;
	   while(low<=high)
	   {
		   m=(high+low)/2;e++;
           if(LT(L.r[0].key,L.r[m].key)==OK)
		   {
			   high=m-1;
		   }
		   else
		   {
			   low=m+1;
		   }
	   }
	   for(j=i-1;j>=high+1;j--)
		   L.r[j+1]=L.r[j];
	   L.r[high+1]=L.r[0];d++;
	}
	c=e;
}
int InitList_Sq(SqList &L,int n,int b[10000])//构造线性表
{
	int i;
	L.length=0;
	for(i=1;i<=n;i++)
	{  
	   L.r[i].key=b[i-1];
        ++L.length;
	}
	
	return OK;
}

int Load_Sq(SqList &L)//输出线性表，后面的用到
{
	int i;
	for(i=1;i<=L.length;i++) 
		printf("%d ",L.r[i].key);
	printf("\n");
	return OK;
}

void main()
{
    int n,i,a[7],m,t,f,j;//m为数据量的选择,t为测试数据的数量
    int b[10000];
	int ii,jj;
	int flag[6]={10,30,50,100,300,500};
	long c[7]={0,0,0,0,0,0,0},d[7]={0,0,0,0,0,0,0};
	SqList L,L1,L2,L3,L4,L5,L6,L7,T;


	//*********************************************************
	printf("***********************************************************\n");
	printf("***************    各类排序算法分析程序   *****************\n");
	printf("****************************   ----ocean  *****************\n");
	printf("***********************************************************\n");
	printf("\n");
	printf("\n");
	printf("  请选择需要测试的排序算法：\n");
	printf("1.直接插入排序\n");
	printf("2.简单选择排序\n");
	printf("3.快速排序\n");
	printf("4.堆排序\n");
	printf("5.归并排序\n");
	printf("6.希尔排序\n");
	printf("7.折半插入排序\n");
	printf("  请先输入需要比较算法的个数，最多可同时选择7种算法一起比较:");
	
	scanf("%d",&n);
	printf("请输入输入 %d 个要比较的算法序号(用空格隔开，回车结束)：\n",n);
	for(i=0;i<n;i++)
		scanf("%d",&a[i]);
	printf("\n");
	printf("*************************************************************\n");
	printf("****************  请选择要测试的数据个数  *******************\n");
	printf("1....10个数据\n");
	printf("2....30个数据\n");
	printf("3....50个数据\n");
	printf("4....100个数据\n");
    printf("5....300个数据\n");
	printf("6....500个数据\n");
	printf("  请选择需要比较的数据量:\n");

	scanf("%d",&m);
	printf("**************************************************************\n");
	printf("1....%d个顺序数据\n",flag[m-1]);
	printf("2....%d个逆序数据\n",flag[m-1]);
	printf("3....%d个随机数据\n",flag[m-1]);
	printf("请选择：");
	scanf("%d",&f);

	printf("\n");
	printf("***************************************************************\n");
	printf("**************      算法比较的结果     ************************\n");
	if(f==3)
	{
		switch(m)
		{
		case 1:{t=10;
				 srand((unsigned int)time(0));//调用rand()函数前，设置好seed，系统时间作为seed，这样就不会每次生成相同的随机数了
				 for(i=0;i<t;i++)
					 b[i]=rand()%100;
			   }break;
		case 2:{t=30;
				 srand((unsigned int)time(0));
				 for(i=0;i<t;i++)
					 b[i]=rand()%100;
			   }break;
		case 3:{t=50;
				 srand((unsigned int)time(0));
				 for(i=0;i<t;i++)
					 b[i]=rand()%200;
			   }break;
		case 4:{t=100;
				 srand((unsigned int)time(0));
				 for(i=0;i<t;i++)
					 b[i]=rand()%1000;
			   }break;
	   case 5:{t=300;
				 srand((unsigned int)time(0));
				 for(i=0;i<t;i++)
					 b[i]=rand()%3000;
			   }break;
		case 6:{t=500;
				 srand((unsigned int)time(0));
				 for(i=0;i<t;i++)
					 b[i]=rand()%3000;
			   }break;
		}
	}
	else if(f==1)
	{
		for(i=0;i<flag[m-1];i++)
			b[i]=i;
	}
	else  if(f==2)
	{
		for(i=flag[m-1],j=0;i>0;j++,i--)
			b[j]=i;
	}
	

	for(i=0;i<n;i++){
		switch(a[i]){
		case 1:{//直接插入排序
               InitList_Sq(L1,flag[m-1],b);      //初始化线性表
                InsertSort(L1,c[a[i]],d[a[i]]);
				printf("直接插入排序：\n");
				printf("比较次数：%ld   交换次数：%ld \n",c[a[i]],d[a[i]]);
			   }break;
		case 2:{//简单选择排序
               InitList_Sq(L2,flag[m-1],b);
               SelectSort(L2,c[a[i]],d[a[i]]);
			   printf("简单选择排序：\n");
			   printf("比较次数：%ld  交换次数：%ld  \n",c[a[i]],d[a[i]]);
			   }break;
        case 3:{//快速排序
			//SqList L3;
			InitList_Sq(L3,flag[m-1],b);
			QSort(L3,1,flag[m-1],c[a[i]],d[a[i]]);
			printf("快速排序：\n");
			printf("比较次数: %ld  交换次数：%ld  \n",c[a[i]],d[a[i]]);
			   }break;
		case 4:{//堆排序
			InitList_Sq(L4,flag[m-1],b);
            HeapSort(L4,c[a[i]],d[a[i]]);
            	printf("堆排序：\n");
				printf("比较次数: %ld  交换次数：%ld  \n",c[a[i]],d[a[i]]);
			   }break;
		case 5:{//归并排序
			InitList_Sq(L5,flag[m-1],b);
             MergeSort(L5,T,c[a[i]],d[a[i]]);
			 	printf("归并排序：\n");
				printf("比较次数: %ld  交换次数：%ld  \n",c[a[i]],d[a[i]]);
			   }break;
		case 6:{//希尔排序
			//	SqList L6;
				int u=4,dlta[4]={5,3,2,1};
				InitList_Sq(L6,flag[m-1],b);
				ShellSort(L6,dlta,u,c[a[i]],d[a[i]]);
			 	printf("希尔排序：\n");
				printf("比较次数: %ld  交换次数：%ld  \n",c[a[i]],d[a[i]]);
			   }break;
		case 7:{//折半插入排序
			InitList_Sq(L7,flag[m-1],b);
	        BInsertSort(L7,c[a[i]],d[a[i]]);
			printf("折半插入排序：\n");
			printf("比较次数: %ld  交换次数：%ld  \n",c[a[i]],d[a[i]]);
			   }break;
		}
		
	}
	printf("***************************************************************\n");
	printf("**************         查看数据        ************************\n");
	printf("\n");

	printf("是否显示排列前数据 输入1，是 输入2，否\n");
	scanf("%d",&ii);
	switch(ii){
		case 1:	
			printf("***************************************************************\n");
			printf("**************      排序前的数据顺序    ************************\n");
			for(i=0;i<flag[m-1];i++)
				   printf("%d ",b[i]);
				   break;
		case 2:break;
	}
	printf("\n");
	printf("***************************************************************\n");
	printf("**************         查看数据        ************************\n");
	printf("是否显示排列后数据 输入1，是 输入2，否\n");
     scanf("%d",&jj);
	 switch(jj){
	 case 1:{
			//SqList L;
			printf("***************************************************************\n");
			printf("**************       排序后的结果     ************************\n");
			InitList_Sq(L,flag[m-1],b);
			QSort(L,1,flag[m-1],c[a[i]],d[a[i]]);      //  用快速排序做一次排序后的输出
			 Load_Sq(L);
			}
			 break;
	 case 2:break;
	 }
	printf("请按任意键退出......");
	getch();
}
💿 文件大小 4 K
👤 上传用户 xiao11tian
📂 所属分类数据结构
📄 代码行数 453 行
💻 语言类型 C++
🏷️ 相关标签

#排序算法 #代码 #比较
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -