刚学C时写的程序，实现了冒泡，选择，插入，希尔，快速和归并排序，并对此6种排序算法进行了简单的效率比较。
#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; }
