资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

排序综合(C++版)-创新互联

目录

创新互联于2013年成立,是专业互联网技术服务公司,拥有项目成都网站设计、成都网站建设网站策划,项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命,1280元城阳做网站,已为上家服务,为城阳各地企业和个人服务,联系电话:18982081108

排序综合                                           

一、问题描述

二、运行环境说明 

三、代码段 

四、效果展示 


排序综合                                           

备注:大二(上)数据结构课程设计B题

一、问题描述

给定N个(长整型范围内的)整数,要求输出从小到大排序后的结果

本题旨在测试各种排序算法在各种数据情况下的表现

各组测试数据特点如下:

·  数据1:11个不相同的整数;

·  数据2:1000个随机整数;

·  数据3:10000个随机整数;

·  数据4:100000个随机整数;

·  数据5:100000个顺序整数;

·  数据6:100000个逆序整数

输入格式:

第一行给出正整数N(N≤10​0000)

随后一行给出N个(长整型范围内的)整数,其间以空格分隔

输出格式:

在一行中输出从小到大排序后的结果,数字间以1个空格分隔

输入样例:

11

4 981 10 -17 0 -20 29 50 8 43 -5

输出样例:

-20 -17 -5 0 4 8 10 29 43 50 981

【测试任务】

(1)按上述输入样例的格式生成数据1~数据6这6组数据集,

分别存储到data1.txt ~ data6.txt这6个文件中

(2)实现以下6种排序算法:

  直接插入排序、希尔排序、起泡排序、快速排序、简单选择排序、堆排序

(3)在主函数中分别调用上述排序函数,对data1.txt ~ data6.txt文件中的数据进行排序,

  并记录不同排序算法对不同数据集进行排序的耗时,将耗时输出到显示器,

  并将排序结果按输出样例格式输出到result1.txt ~ result6.txt这6个文件中

二、运行环境说明 

三、代码段 
#include#include
#includeusing namespace std;

//--------------------------------------------------------------------------------------------

void InsertSort(int arr[], int length) //直接插入排序 
{
    if (arr == nullptr || length<= 0)
        return;
    for(int i=2;i<=length;i++)
      if(arr[i]=1 && arr[0]=1 && arr[0]0 && flag)
	  {
	  	flag=false;
	  	for(int j=1;j<=m;j++)
	  	  if(arr[j]>arr[j+1])
	  	    {
	  	    	flag=true;
	  	    	int tem=arr[j];
	  	    	arr[j]=arr[j+1];
	  	    	arr[j+1]=tem;
			  }
	    m--;
	  }
} 

void QuickSort(int q[],int l,int r) //快速排序 
{
    if(l>=r)  return;
    
    int i=l-1,j=r+1,x=q[l+r>>1];
    while(ix);
          if(i0;i--)
	  HeapAdjust(arr,i,n);
}
void HeapSort(int arr[], int length) //堆排序 
{
	CreatHeap(arr,length);
	for(int i=length;i>1;i--)
	  {
	  	int tem=arr[1];
	  	arr[1]=arr[i];
	  	arr[i]=tem;
		HeapAdjust(arr,1,i-1);
	  }
}

//--------------------------------------------------------------------------------------------

void GetData()                                                                   //获取整数数据函数 
{
	FILE *fp1,*fp2,*fp3,*fp4,*fp5,*fp6;           //文件指针 
	
	fp1 = fopen("data1.txt", "w");
    fprintf(fp1,"11\n");
    fclose(fp1);
    fp1 = fopen("data1.txt", "a");
    fprintf(fp1,"4 981 10 -17 0 -20 29 50 8 43 -5");
    fclose(fp1);
	
	fp2 = fopen("data2.txt", "w");
    fprintf(fp2,"1000\n");
    fclose(fp2);
    fp2 = fopen("data2.txt", "a");
	srand((int)time(0));                          //随机种子 
    for(int i=1;i<=1000;i++)
      fprintf(fp2,"%d ",((rand()<<15)+rand())%10000);            //随机整数的范围为[0,10000)
	fclose(fp2);
	
	fp3 = fopen("data3.txt", "w");
    fprintf(fp3,"10000\n");
    fclose(fp3);
    fp3 = fopen("data3.txt", "a");
	srand((int)time(0));                          //随机种子 
    for(int i=1;i<=10000;i++)
      fprintf(fp3,"%d ",((rand()<<15)+rand())%100000);           //随机整数的范围为[0,100000)
	fclose(fp3);
	
	fp4 = fopen("data4.txt", "w");
    fprintf(fp4,"100000\n");
    fclose(fp4);
    fp4 = fopen("data4.txt", "a");
	srand((int)time(0));                          //随机种子 
    for(int i=1;i<=100000;i++)
      fprintf(fp4,"%d ",((rand()<<15)+rand())%1000000);          //随机整数的范围为[0,1000000)
	fclose(fp4);
	
	fp5 = fopen("data5.txt", "w");
    fprintf(fp5,"100000\n");
    fclose(fp5);
    fp5 = fopen("data5.txt", "a");
    for(int i=1;i<=100000;i++)
      fprintf(fp5,"%d ",i);      //100000个顺序整数 
    fclose(fp5);
    
    fp6 = fopen("data6.txt", "w");
    fprintf(fp6,"100000\n");
    fclose(fp6);
    fp6 = fopen("data6.txt", "a");
    for(int i=100000;i>=1;i--)
      fprintf(fp6,"%d ",i);      //100000个逆序整数 
    fclose(fp6);
}

//--------------------------------------------------------------------------------------------

void InitData(int R1[],int R2[],int R3[],int R4[],int R5[],int R6[])             //读取整数数据函数
{
	FILE *fp1,*fp2,*fp3,*fp4,*fp5,*fp6;             //文件指针
	
    if((fp1 = fopen("data1.txt", "r")) == NULL)
       cout<< "不能打开文件data1.txt"<< endl; 
    else
	{
	  int count1=0;
	  while(!feof(fp1))
	     {
		   fscanf(fp1,"%d",&R1[count1]);
		   count1++;
	     }
	}
	fclose(fp1);
	
	if((fp2 = fopen("data2.txt", "r")) == NULL)
       cout<< "不能打开文件data2.txt"<< endl; 
    else
	{
	  int count2=0;
	  while(!feof(fp2))
	     {
		   fscanf(fp2,"%d",&R2[count2]);
		   count2++;
	     }
	}
	fclose(fp2);
	
	if((fp3 = fopen("data3.txt", "r")) == NULL)
       cout<< "不能打开文件data3.txt"<< endl; 
    else
	{
	  int count3=0;
	  while(!feof(fp3))
	     {
		   fscanf(fp3,"%d",&R3[count3]);
		   count3++;
	     }
	}
	fclose(fp3);
	
	if((fp4 = fopen("data4.txt", "r")) == NULL)
       cout<< "不能打开文件data4.txt"<< endl; 
    else
	{
	  int count4=0;
	  while(!feof(fp4))
	     {
		   fscanf(fp4,"%d",&R4[count4]);
		   count4++;
	     }
	}
	fclose(fp4);
	
	if((fp5 = fopen("data5.txt", "r")) == NULL)
       cout<< "不能打开文件data5.txt"<< endl; 
    else
	{
	  int count5=0;
	  while(!feof(fp5))
	     {
		   fscanf(fp5,"%d",&R5[count5]);
		   count5++;
	     }
	}
	fclose(fp5);
	
	if((fp6 = fopen("data6.txt", "r")) == NULL)
       cout<< "不能打开文件data6.txt"<< endl; 
    else
	{
	  int count6=0;
	  while(!feof(fp6))
	     {
		   fscanf(fp6,"%d",&R6[count6]);
		   count6++;
	     }
	}
	fclose(fp6);
}

//--------------------------------------------------------------------------------------------

double VariousSort(char c, int R[], int length)
{
	double t;
	clock_t startTime,endTime;
	
	if(c=='I')//直接插入排序
	  {
	  	startTime = clock(); InsertSort(R,length); endTime = clock();
        t = (double)(endTime - startTime)/CLOCKS_PER_SEC;
        return t;
	  }
	else if(c=='M')//希尔排序
	  {
	  	int len=3;
	    int dt[]={5,3,1};
	    startTime = clock(); 
	    MainShellSort(R,length,dt,len);
		endTime = clock();
        t = (double)(endTime - startTime)/CLOCKS_PER_SEC;
        return t;
	  }
	else if(c=='B')//冒泡排序
	  {
	  	startTime = clock(); BubbleSort(R,length); endTime = clock();
        t = (double)(endTime - startTime)/CLOCKS_PER_SEC;
        return t;
	  }
	else if(c=='Q')//快速排序
	  {
	  	startTime = clock(); QuickSort(R,1,length); endTime = clock();
        t = (double)(endTime - startTime)/CLOCKS_PER_SEC;
        return t;
	  }
	else if(c=='S')//简单选择排序
	  {
	  	startTime = clock(); SelectSort(R,length); endTime = clock();
        t = (double)(endTime - startTime)/CLOCKS_PER_SEC;
        return t;
	  }
	else//堆排序
	  {
	  	startTime = clock(); HeapSort(R,length); endTime = clock();
        t = (double)(endTime - startTime)/CLOCKS_PER_SEC;
        return t;
	  }
}

//--------------------------------------------------------------------------------------------

void GetResult(int R1[],int R2[],int R3[],int R4[],int R5[],int R6[])            //获取排序结果函数
{
	double t[10];
	
	InitData(R1,R2,R3,R4,R5,R6);
	t[1]=VariousSort('I', R1, 11);
	t[2]=VariousSort('I', R2, 1000);
	t[3]=VariousSort('I', R3, 10000);
	t[4]=VariousSort('I', R4, 100000);
	t[5]=VariousSort('I', R5, 100000);
	t[6]=VariousSort('I', R6, 100000);
	printf("直接插入排序:\n");
	for(int i=1;i<=6;i++)
	  printf("排序数据%d用时%lf秒\n",i,t[i]);
	printf("对六类数据排序所用总时间为%lf秒\n",t[1]+t[2]+t[3]+t[4]+t[5]+t[6]);
	puts("");
	  
	InitData(R1,R2,R3,R4,R5,R6);
	t[1]=VariousSort('M', R1, 11);
	t[2]=VariousSort('M', R2, 1000);
	t[3]=VariousSort('M', R3, 10000);
	t[4]=VariousSort('M', R4, 100000);
	t[5]=VariousSort('M', R5, 100000);
	t[6]=VariousSort('M', R6, 100000);
	printf("希尔排序:\n");
	for(int i=1;i<=6;i++)
	  printf("排序数据%d用时%lf秒\n",i,t[i]);
	printf("对六类数据排序所用总时间为%lf秒\n",t[1]+t[2]+t[3]+t[4]+t[5]+t[6]);
	puts("");
	  
	InitData(R1,R2,R3,R4,R5,R6);
	t[1]=VariousSort('B', R1, 11);
	t[2]=VariousSort('B', R2, 1000);
	t[3]=VariousSort('B', R3, 10000);
	t[4]=VariousSort('B', R4, 100000);
	t[5]=VariousSort('B', R5, 100000);
	t[6]=VariousSort('B', R6, 100000);
	printf("冒泡排序:\n");
	for(int i=1;i<=6;i++)
	  printf("排序数据%d用时%lf秒\n",i,t[i]);
	printf("对六类数据排序所用总时间为%lf秒\n",t[1]+t[2]+t[3]+t[4]+t[5]+t[6]);
	puts("");
	  
	InitData(R1,R2,R3,R4,R5,R6);
	t[1]=VariousSort('Q', R1, 11);
	t[2]=VariousSort('Q', R2, 1000);
	t[3]=VariousSort('Q', R3, 10000);
	t[4]=VariousSort('Q', R4, 100000);
	t[5]=VariousSort('Q', R5, 100000);
	t[6]=VariousSort('Q', R6, 100000);
	printf("快速排序:\n");
	for(int i=1;i<=6;i++)
	  printf("排序数据%d用时%lf秒\n",i,t[i]);
	printf("对六类数据排序所用总时间为%lf秒\n",t[1]+t[2]+t[3]+t[4]+t[5]+t[6]);
	puts("");
	  
	InitData(R1,R2,R3,R4,R5,R6);
	t[1]=VariousSort('S', R1, 11);
	t[2]=VariousSort('S', R2, 1000);
	t[3]=VariousSort('S', R3, 10000);
	t[4]=VariousSort('S', R4, 100000);
	t[5]=VariousSort('S', R5, 100000);
	t[6]=VariousSort('S', R6, 100000);
	printf("简单选择排序:\n");
	for(int i=1;i<=6;i++)
	  printf("排序数据%d用时%lf秒\n",i,t[i]);
	printf("对六类数据排序所用总时间为%lf秒\n",t[1]+t[2]+t[3]+t[4]+t[5]+t[6]);
	puts("");
	  
	InitData(R1,R2,R3,R4,R5,R6);
	t[1]=VariousSort('H', R1, 11);
	t[2]=VariousSort('H', R2, 1000);
	t[3]=VariousSort('H', R3, 10000);
	t[4]=VariousSort('H', R4, 100000);
	t[5]=VariousSort('H', R5, 100000);
	t[6]=VariousSort('H', R6, 100000);
	printf("堆排序:\n");
	for(int i=1;i<=6;i++)
	  printf("排序数据%d用时%lf秒\n",i,t[i]);
	printf("对六类数据排序所用总时间为%lf秒\n",t[1]+t[2]+t[3]+t[4]+t[5]+t[6]);
	  
	FILE *fp1,*fp2,*fp3,*fp4,*fp5,*fp6;             //文件指针
	
	fp1 = fopen("result1.txt", "w");
    for(int i=1;i<=11;i++)
      fprintf(fp1,"%d ",R1[i]);           
	fclose(fp1);
	
	fp2 = fopen("result2.txt", "w");
    for(int i=1;i<=1000;i++)
      fprintf(fp2,"%d ",R2[i]);           
	fclose(fp2);
	
	fp3 = fopen("result3.txt", "w");
    for(int i=1;i<=10000;i++)
      fprintf(fp3,"%d ",R3[i]);           
	fclose(fp3);
	
	fp4 = fopen("result4.txt", "w");
    for(int i=1;i<=100000;i++)
      fprintf(fp4,"%d ",R4[i]);           
	fclose(fp4);
	
	fp5 = fopen("result5.txt", "w");
    for(int i=1;i<=100000;i++)
      fprintf(fp5,"%d ",R5[i]);           
	fclose(fp5);
	
	fp6 = fopen("result6.txt", "w");
    for(int i=1;i<=100000;i++)
      fprintf(fp6,"%d ",R6[i]);           
	fclose(fp6);
}

//--------------------------------------------------------------------------------------------

int main()
{
	int R1[20],R2[1010],R3[10010],R4[100010],R5[100010],R6[100010];
	  
	GetData();
	
	printf("六类数据预览:\n");
	printf("数据1:11个不相同的整数\n");
	printf("数据2:1,000个[0,10000)范围内随机整数\n");
	printf("数据3:10,000个[0,100000)范围内随机整数\n");
	printf("数据4:100,000个[0,1000000)范围内随机整数\n");
	printf("数据5:[1,100000]范围内所有整数从小到大排列\n");
	printf("数据6:[1,100000]范围内所有整数从大到小排列\n\n");
	printf("接下来将调用六类排序方法对以上六类数据进行从小到大排序,并测算排序所用时间!\n\n");
	
	GetResult(R1,R2,R3,R4,R5,R6);
	
	return 0;
}
四、效果展示 

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


网站栏目:排序综合(C++版)-创新互联
标题网址:http://cdkjz.cn/article/cdsgig.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220