排序综合（C++版）
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
目录
排序综合
备注大二上数据结构课程设计B题
一、问题描述
给定N个长整型范围内的整数要求输出从小到大排序后的结果
本题旨在测试各种排序算法在各种数据情况下的表现
各组测试数据特点如下
· 数据111个不相同的整数
· 数据21000个随机整数
· 数据310000个随机整数
· 数据4100000个随机整数
· 数据5100000个顺序整数
· 数据6100000个逆序整数
输入格式
第一行给出正整数NN≤100000
随后一行给出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<iostream>
#include<algorithm>
#include <ctime>
using namespace std;
//--------------------------------------------------------------------------------------------
void InsertSort(int arr[], int length) //直接插入排序
{
if (arr == nullptr || length <= 0)
return;
for(int i=2;i<=length;i++)
if(arr[i]<arr[i-1])
{
arr[0]=arr[i];
arr[i]=arr[i-1];
int j=i-2;
for(;j>=1 && arr[0]<arr[j];j--)
arr[j+1]=arr[j];
arr[j+1]=arr[0];
}
}
void MinShellSort(int arr[], int length, int dk)
{
for(int i=dk+1;i<=length;i++)
if(arr[i]<arr[i-dk])
{
arr[0]=arr[i];
int j=i-dk;
for(;j>=1 && arr[0]<arr[j];j-=dk)
arr[j+dk]=arr[j];
arr[j+dk]=arr[0];
}
}
void MainShellSort(int arr[], int length,int dt[],int len) //希尔排序
{
for(int k=0;k<len;k++)
MinShellSort(arr,length,dt[k]);
}
void BubbleSort(int arr[], int length) //冒泡排序
{
bool flag=true;
int m=length-1;
while(m>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(i<j)
{
do i++; while(q[i]<x);
do j--; while(q[j]>x);
if(i<j) swap(q[i],q[j]);
}
QuickSort(q,l,j);
QuickSort(q,j+1,r);
}
void SelectSort(int arr[], int length) //简单选择排序
{
for(int i=1;i<length;i++)
{
int k=i;
for(int j=i+1;j<=length;j++)
if(arr[j]<arr[k])
k=j;
if(k!=i)
{
int tem=arr[i];
arr[i]=arr[k];
arr[k]=tem;
}
}
}
void HeapAdjust(int arr[],int s,int m)
{
int rc=arr[s];
for(int j=2*s;j<=m;j*=2)
{
if(j<m && arr[j]<arr[j+1]) j++;
if(rc>=arr[j]) break;
arr[s]=arr[j];
s=j;
}
arr[s]=rc;
}
void CreatHeap(int arr[], int length)
{
int n=length;
for(int i=n/2;i>0;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("数据111个不相同的整数\n");
printf("数据21,000个[0,10000)范围内随机整数\n");
printf("数据310,000个[0,100000)范围内随机整数\n");
printf("数据4100,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;
}四、效果展示
