[C] 纯文本查看 复制代码
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <windows.h>
int str1[105],str2[105],str3[105],str4[105],str5[105];
int str1_1[105],str1_2[105],str1_3[105],str1_4[105],str1_5[105],str1_6[105];
int str2_1[105],str2_2[105],str2_3[105],str2_4[105],str2_5[105],str2_6[105];
int str3_1[105],str3_2[105],str3_3[105],str3_4[105],str3_5[105],str3_6[105];
int str4_1[105],str4_2[105],str4_3[105],str4_4[105],str4_5[105],str4_6[105];
int str5_1[105],str5_2[105],str5_3[105],str5_4[105],str5_5[105],str5_6[105];
int k,k1,k2,k3,k4,k5;
int qcompare,qmov;
int gcompare,gmov;
int avbubblingc,avselectc,avinsertionc,avshellc,avquickc,avmergec;
int avbubblingm,avselectm,avinsertionm,avshellm,avquickm,avmergem;
void randint() //产生随机数数组
{
int i,j;
srand((unsigned)time(NULL));
for(i=0;i<100;i++) //模型数组
{
str1[i]=rand()%101;
str2[i]=rand()%101;
str3[i]=rand()%101;
str4[i]=rand()%101;
str5[i]=rand()%101;
}
for(j=0;j<100;j++)
{
str1_1[j] = str1[j];
str1_2[j] = str1[j];
str1_3[j] = str1[j];
str1_4[j] = str1[j];
str1_5[j] = str1[j];
str1_6[j] = str1[j];
}
for(j=0;j<100;j++)
{
str2_1[j] = str2[j];
str2_2[j] = str2[j];
str2_3[j] = str2[j];
str2_4[j] = str2[j];
str2_5[j] = str2[j];
str2_6[j] = str2[j];
}
for(j=0;j<100;j++)
{
str3_1[j] = str3[j];
str3_2[j] = str3[j];
str3_3[j] = str3[j];
str3_4[j] = str3[j];
str3_5[j] = str3[j];
str3_6[j] = str3[j];
}
for(j=0;j<100;j++)
{
str4_1[j] = str4[j];
str4_2[j] = str4[j];
str4_3[j] = str4[j];
str4_4[j] = str4[j];
str4_5[j] = str4[j];
str4_6[j] = str4[j];
}
for(j=0;j<100;j++)
{
str5_1[j] = str5[j];
str5_2[j] = str5[j];
str5_3[j] = str5[j];
str5_4[j] = str5[j];
str5_5[j] = str5[j];
str5_6[j] = str5[j];
}
}
void printrand() //打印生成的随机数组
{
int i;
printf("第一组\n");
for(i=0;i<100;i++)
{
printf("%d ",str1[i]);
}
printf("\n------------------------------------\n");
printf("第二组\n");
for(i=0;i<100;i++)
{
printf("%d ",str2[i]);
}
printf("\n------------------------------------\n");
printf("第三组\n");
for(i=0;i<100;i++)
{
printf("%d ",str3[i]);
}
printf("\n------------------------------------\n");
printf("第四组\n");
for(i=0;i<100;i++)
{
printf("%d ",str4[i]);
}
printf("\n------------------------------------\n");
printf("第五组\n");
for(i=0;i<100;i++)
{
printf("%d ",str5[i]);
}
printf("\n------------------------------------\n");
}
void bubbling_sort(int str[],int n) //冒泡排序
{
int i,j,temp,compare = 0,mov = 0;
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
compare++;
if(str[i]>str[j])
{
temp = str[i];
str[i] = str[j];
str[j] = temp;
mov = mov + 3;
}
}
}
printf("第%d组数据： 比较次数->%d 移动次数%d\n",k++,compare,mov);
avbubblingc = avbubblingc + compare;
avbubblingm = avbubblingm + mov;
}
void select_sort(int str[],int n) //选择排序
{
int i,j,compare = 0,mov = 0;
for(i=0;i<n;i++) //进行n-1轮遍历
{
int Min = str[i]; //先设成最小的
int temp;
int index = i; //记录下标
for(j=i+1;j<n;j++) //从i+1开始找最小值
{
compare++;
if(str[j]<Min)
{
Min = str[j];
index = j; //记录最小值的下标
}
}
if(i!=index) //不等于就交换
{
temp = str[i]; //以下3行为交换位置
str[i] = Min;
str[index] = temp;
mov = mov + 3;
}
}
printf("第%d组数据 比较次数->%d 移动次数->%d\n",k1++,compare,mov);
avselectc = avselectc + compare;
avselectm = avselectm + mov;
}
void insertion_sort(int str[],int n) //插入排序
{
int i,j,tnum;
int compare = 0,mov = 0;
for(i=1;i<n;i++) //遍历n-1次就ok
{
tnum = str[i]; //先把要插入的数存在tnum
for(j=i-1;j>=0&&tnum<str[j];j--) //从后往前比
{
compare++;
str[j+1] = str[j]; //移动元素
mov++;
}
str[j+1] = tnum; //找到插入位置了
}
printf("第%d组数据 比较次数->%d 移动次数->%d\n",k2++,compare,mov);
avinsertionc = avinsertionc + compare;
avinsertionm = avinsertionm + mov;
}
void shell_sort(int str[],int n)
{
int group,i,j,k,temp;
int compare = 0,mov = 0;
for(group=n/2;group>0;group=group/2) //分组
{
for(i=0;i<group;i++) //有i组
{
for(j=i+group;j<n;j=j+group) //对这些组的元素进行插入排序
{
compare++;
if(str[j]<str[j-group])
{
temp = str[j]; //小的值放到temp
k = j - group; //记录前面那个大的值的下标
while(k>=0&&str[k]>temp) //从后往前找
{
str[k+group] = str[k]; //移动元素
k = k - group;
mov++;
}
str[k+group] = temp; //找到插入位置了
}
}
}
}
printf("第%d组数据 比较次数->%d 移动次数->%d\n",k3++,compare,mov);
avshellc = avshellc + compare;
avshellm = avshellm + mov;
}
void quick_sort(int str[],int l,int r) //分治快排
{
int i = l,j = r,x = str[l];
if(l>=r) return;
while(i!=j)
{
while(i<j&&str[j]>=x) //右到左找第一个小于x的数
{
qcompare++;
j--;
}
if(i<j)
{
str[i] = str[j];
qmov++;
}
while(i<j&&str[i]<=x) //左到右找第一个大于x的数
{
qcompare++;
i++;
}
if(i<j)
{
str[j] = str[i];
qmov++;
}
}
str[i] = x; //左右指针重合了就是x
quick_sort(str,l,i-1); //递归左边
quick_sort(str,i+1,r); //递归右边
}
void merge_array(int str[],int first,int mid,int last,int str2[]) //合并两个有序序列-----并
{
int i = first,m = mid,n = last;
int j = mid + 1;
int k = 0;
while(i<=m&&j<=n) //比较看谁小就入谁
{
if(str[i]<=str[j])
{
gcompare++;
str2[k++] = str[i++];
gmov++;
}
else
{
gcompare++;
str2[k++] = str[j++];
gmov++;
}
}
while(i<=m) //i(左边)有剩
{
str2[k++] = str[i++];
gmov++;
}
while(j<=n) //j(右边)有剩
{
str2[k++] = str[j++];
gmov++;
}
for(i=0;i<k;i++) //合并好的整个序列复制到原序列中
{
str[first+i] = str2[i];
gmov++;
}
}
void merge_sort(int str[],int first,int last,int str2[])
{
if(first<last)
{
int mid = (first+last) / 2; //-----归
merge_sort(str,first,mid,str2); //左边有序
merge_sort(str,mid+1,last,str2); //右边有序
merge_array(str,first,mid,last,str2); //将两个有序序列合并
}
}
void windows() //菜单
{
printf("!------------------------欢迎使用LSA内部排序测试系统--------------------------!\n\n\n");
printf("1-显示生成的5组随机数组 查看冒泡排序的效率对比-2\n");
printf("3-查看选择排序的效率对比 查看插入排序的效率对比-4\n");
printf("5-查看希尔排序的效率对比 查看快速排序的效率对比-6\n");
printf("7-查看归并排序的效率对比 查看6种的效率对比-8\n");
printf("9-版权声明 退出系统-10\n");
}
char retu() //返回选择
{
char choose1;
printf("r-返回菜单 e-退出系统\n");
scanf("%c",&choose1);
return choose1;
}
void exitsort() //退出系统
{
printf("感谢您对LSA内部排序测试系统的支持，欢迎再次光临！\n");
exit(0);
}
void choo()
{
int choose;
int str2[105];
s1:windows();
while(1)
{
scanf("%d",&choose);
getchar();
switch(choose)
{
case 1:system("CLS");
printrand();
if(retu()=='r')
{
system("CLS");
goto s1;
}
else
{
system("CLS");
exitsort();
}
break;
case 2:system("CLS");
printf("冒泡排序对5组数据的效率对比\n\n");
bubbling_sort(str1_1,100);
bubbling_sort(str2_1,100);
bubbling_sort(str3_1,100);
bubbling_sort(str4_1,100);
bubbling_sort(str5_1,100);
if(retu()=='r')
{
system("CLS");
goto s1;
}
else
{
system("CLS");
exitsort();
}
break;
case 3:system("CLS");
printf("选择排序对5组数据的效率对比\n");
select_sort(str1_2,100);
select_sort(str2_2,100);
select_sort(str3_2,100);
select_sort(str4_2,100);
select_sort(str5_2,100);
if(retu()=='r')
{
system("CLS");
goto s1;
}
else
{
system("CLS");
exitsort();
}
break;
case 4:system("CLS");
printf("插入排序对5组数据的效率对比\n");
insertion_sort(str1_3,100);
insertion_sort(str2_3,100);
insertion_sort(str3_3,100);
insertion_sort(str4_3,100);
insertion_sort(str5_3,100);
if(retu()=='r')
{
system("CLS");
goto s1;
}
else
{
system("CLS");
exitsort();
}
break;
case 5:system("CLS");
printf("希尔排序对5组数据的效率对比\n");
shell_sort(str1_4,100);
shell_sort(str2_4,100);
shell_sort(str3_4,100);
shell_sort(str4_4,100);
shell_sort(str5_4,100);
if(retu()=='r')
{
system("CLS");
goto s1;
}
else
{
system("CLS");
exitsort();
}
break;
case 6:system("CLS");
printf("快速排序对5组数据的效率对比\n");
quick_sort(str1_5,0,99); printf("第%d组数据 比较次数->%d 移动次数->%d\n",k4++,qcompare,qmov); avquickc = avquickc + qcompare; avquickm = avquickm + qmov; qcompare = 0,qmov = 0;
quick_sort(str2_5,0,99); printf("第%d组数据 比较次数->%d 移动次数->%d\n",k4++,qcompare,qmov); avquickc = avquickc + qcompare; avquickm = avquickm + qmov; qcompare = 0,qmov = 0;
quick_sort(str3_5,0,99); printf("第%d组数据 比较次数->%d 移动次数->%d\n",k4++,qcompare,qmov); avquickc = avquickc + qcompare; avquickm = avquickm + qmov; qcompare = 0,qmov = 0;
quick_sort(str4_5,0,99); printf("第%d组数据 比较次数->%d 移动次数->%d\n",k4++,qcompare,qmov); avquickc = avquickc + qcompare; avquickm = avquickm + qmov; qcompare = 0,qmov = 0;
quick_sort(str5_5,0,99); printf("第%d组数据 比较次数->%d 移动次数->%d\n",k4++,qcompare,qmov); avquickc = avquickc + qcompare; avquickm = avquickm + qmov; qcompare = 0,qmov = 0;
if(retu()=='r')
{
system("CLS");
goto s1;
}
else
{
system("CLS");
exitsort();
}
break;
case 7:system("CLS");
printf("归并排序对5组数据的效率对比\n");
merge_sort(str1_6,0,99,str2); printf("第%d组数据 比较次数->%d 移动次数->%d\n",k5++,gcompare,gmov); avmergec = avmergec + gcompare; avmergem = avmergem + gmov; gcompare = 0,gmov = 0;
merge_sort(str2_6,0,99,str2); printf("第%d组数据 比较次数->%d 移动次数->%d\n",k5++,gcompare,gmov); avmergec = avmergec + gcompare; avmergem = avmergem + gmov; gcompare = 0,gmov = 0;
merge_sort(str3_6,0,99,str2); printf("第%d组数据 比较次数->%d 移动次数->%d\n",k5++,gcompare,gmov); avmergec = avmergec + gcompare; avmergem = avmergem + gmov; gcompare = 0,gmov = 0;
merge_sort(str4_6,0,99,str2); printf("第%d组数据 比较次数->%d 移动次数->%d\n",k5++,gcompare,gmov); avmergec = avmergec + gcompare; avmergem = avmergem + gmov; gcompare = 0,gmov = 0;
merge_sort(str5_6,0,99,str2); printf("第%d组数据 比较次数->%d 移动次数->%d\n",k5++,gcompare,gmov); avmergec = avmergec + gcompare; avmergem = avmergem + gmov; gcompare = 0,gmov = 0;
if(retu()=='r')
{
system("CLS");
goto s1;
}
else
{
system("CLS");
exitsort();
}
break;
case 8:system("CLS");
printf("6种排序对5组数据的效率对比\n");
printf("冒泡排序： 平均比较次数%d 平均移动次数%d\n",avbubblingc/5,avbubblingm/5);
printf("选择排序： 平均比较次数%d 平均移动次数%d\n",avselectc/5,avselectm/5);
printf("插入排序： 平均比较次数%d 平均移动次数%d\n",avinsertionc/5,avinsertionm/5);
printf("希尔排序： 平均比较次数%d 平均移动次数%d\n",avshellc/5,avshellm/5);
printf("快速排序： 平均比较次数%d 平均移动次数%d\n",avquickc/5,avquickm/5);
printf("归并排序： 平均比较次数%d 平均移动次数%d\n",avmergec/5,avmergem/5);
if(retu()=='r')
{
system("CLS");
goto s1;
}
else
{
system("CLS");
exitsort();
}
break;
case 9:system("CLS");
printf("这里是极为重要的版权声明：\n");
printf("LSA内部排序系统允许引用或修改或转载，须注明出处是LSA内部排序系统！\n 请尊重原创!\n 多谢合作!\n");
if(retu()=='r')
{
system("CLS");
goto s1;
}
else
{
system("CLS");
exitsort();
}
break;
case 10:system("CLS");
exitsort();
break;
}
}
}
int main()
{
system("color 12");
randint();
choo();
return 0;
}
发表于 2017-4-7 19:41
|
发表于 2017-4-7 20:58
