对以下两种常用排序算法进行比较:折半插入排序、堆排序(参见教材第九章),比较各算法的关键字比较次数和关键字移动次数。 (1)对以下两种常用排序算法进行比较:折半插入排序、堆排序; (2)使用题目已经提供的五个数组,比较的指标为有关键字参加的比较次数和关键字移动次数; (3)可以设两个全局变量,分别记录比较与移动次数,设法在程序中适当的地方插入计数操作; (4)在主函数中调用菜单函数调试程序。
#include <stdio.h> #include <stdlib.h> #include <time.h> #define Max 100 int p,q,m,n; int menu_select(); void Create(int a[],int d[]); void BinSort(int a[]); void HeapSort(int a[]); void crt_heap(int a[]); void sift(int a[],int k,int m); int menu_select() //菜单驱动程序 { int sn; printf("两种排序算法比较\n"); //显示菜单 printf("==========================\n"); printf("1.生成待排序数组\n"); printf("2.折半插入排序\n"); printf("3.堆排序\n"); printf("0.退出程序\n"); printf("==========================\n"); printf("请选择0--5:"); for(;;) //菜单功能选择 { scanf("%d",&sn); //输入选项 getchar(); if(sn<0 || sn>5) printf("\n 输入选择错误,请重新选择 0--3:"); else break; } return sn; } void Create(int a[],int d[])//随机生成数组函数 { int c,i,j; printf("请输出1-5选择数组:" ); scanf("%d",&c); getchar(); switch(c){ case 1: for(i=0;i<50;i++) a[i]=2*i; for(i=50;i<Max;i++) a[i]=2*i-1; for(j=0;j<Max;j++) d[j]=a[j]; printf("数组1生成成功.\n"); break; case 2: for(i=0;i<50;i++) a[i]=2*i; for(i=50;i<Max;i++) a[i]=2*i-3; for(j=0;j<Max;j++) d[j]=a[j]; printf("数组2生成成功.\n"); break; case 3: for(i=0;i<50;i++) a[i]=2*i; for(i=Max-1;i>=50;i--) a[i]=2*i-1; for(j=0;j<Max;j++) d[j]=a[j]; printf("数组3生成成功.\n"); break; case 4: for(i=0;i<50;i++) a[i]=2*i; for(i=Max-1;i>=50;i--) a[i]=2*i-3; for(j=0;j<Max;j++) d[j]=a[j]; printf("数组4生成成功.\n"); break; case 5: for(i=0;i<50;i++) a[i]=2*(i+100); for(i=50;i<Max;i++) a[i]=3*(i-5); for(j=0;j<Max;j++) d[j]=a[j]; printf("数组5生成成功.\n"); break; } } /* TODO: 折半插入排序算法 功能:编写折半插入排序算法,然后统计关键字的比较次数和移动次数,并输出。 关键字a[0]与a[mid]比对一次,关键字比较次数+1, 关键字位置互换一次,关键字移动次数+1, 输出语句 printf("折半插入排序\n"); printf("关键字比较次数:%d\n",m); printf("关键字移动次数:%d\n",n); 参数:int a[]是排序查找的数组 返回值:空 */ void BinSort(int a[])//折半插入排序算法 { printf("折半插入排序\n"); int i=0,j,x; int low,high,mid; for(i=2;i<Max;++i){ x=a[i]; low=1; high=i-1; while(low<=high){ mid=(low+high)/2; if(x<a[mid]) { high=mid-1; } else low=mid+1; m++; } for(j=i-1;j>=low;--j){ a[j+1]=a[j]; n++; } a[low]=x; } printf("关键字比较次数:%d\n",m); printf("关键字移动次数:%d\n",n); } /* TODO: 堆排序算法 功能:编写堆排序算法,然后统计关键字的比较次数和移动次数,并输出。 关键字比较次数在重建堆的方法——sift方法中已计算,函数中传参直接调用即可; 关键字通过中间变量进行交换,b=a[1],a[1]=a[i],a[i]=b 这样算移动三次位置。 输出语句 printf("堆排序\n"); printf("关键字比较次数:%d\n",p); printf("关键字移动次数:%d\n",q); 参数:int a[]是排序查找的数组 返回值:空 */ void HeapSort(int a[])//堆排序算法 { printf("堆排序\n"); crt_heap(a); int temp,i=0; for(i=Max-1;i>=2;i--){ temp=a[1]; a[1]=a[i]; a[i]=temp; q+=3; sift(a,1,i-1); } printf("关键字比较次数:%d\n",p); printf("关键字移动次数:%d\n",q); } void crt_heap(int a[]) { int n=Max-1,i; for(i=n/2;i>=1;--i) sift(a,i,n); } void sift(int a[],int k,int m) { int sign=0; int t,x,i,j; t=a[k]; x=a[k]; i=k; j=2*i; while(j<=m && !sign) { if(j<m && a[j]<a[j+1]) j=j+1; if(x>=a[j]) sign=1; else{ a[i]=a[j]; q++; i=j; j=2*i; } p+=2; } a[i]=t; } void main() { int a[Max],d[Max]; int i; m=0;n=0;p=0;q=0; for(;;) // 无限循环,选择0 退出 { switch(menu_select()) // 调用菜单函数,按返回值选择功能函数 { case 1: printf("1.生成待排序数组\n"); Create(a,d); break; case 2: printf("2.折半插入排序\n"); BinSort(a); break; case 3: printf("3.堆排序\n"); HeapSort(d); break; case 0: printf("0.退出程序\n"); return; } // switch语句结束 } // for循环结束 } // main()函数结束
打赏
支付宝扫一扫
微信扫一扫