【计算机算法基础】算法程序设计习题.docVIP

算法程序设计 一,比较归并分类和快速分类算法 思想:结合课本中的算法结构,分别计算在数据集相同且分别为随机数,非降序,非增序情况下两种算法所需的时间.数据集为1000000. #includestdio.h #includeconio.h #includestdlib.h #includetime.h #includesys/timeb.h #includelimits.h #define MAX 1000000 //工作数据集为1000000 int A[MAX+2]; //多出的两个为0号和最后一个无穷大 int B[MAX+2]; //B和C保证排序使用的数据集相同,若作为局部变量会造成 int C[MAX+2]; //内存溢出 void MERGESORT(int low,int high) //归并排序 { int mid; if(lowhigh) { mid=(low+high)/2; MERGESORT(low,mid); MERGESORT(mid+1,high); MERGE(low,mid,high); } return; } void MERGE(int low,int mid,int high) //归并两个已分类的集合 { int i,j,k,h; h=i=low,j=mid+1; while(h=midj=high) { if(A[h]=A[j]) { B[i]=A[h]; h++; } else { B[i]=A[j]; j++; } i++; } if(hmid) for(k=j;k=high;k++) {B[i]=A[k];i++;} else for(k=h;k=mid;k++) {B[i]=A[k];i++;} for(k=low;k=high;k++) A[k]=B[k]; return; } void QUICKSORT(int m,int p) //快速排序,将两个函数合为一个 { int v,j,k,temp; v=A[m]; j=m; k=p+1; if(jk) { for(;jk;) { do{ j++; } while(A[j]v); do{ k--; } while(A[k]v); if(jk) { temp=A[j]; A[j]=A[k]; A[k]=temp; } } A[m]=A[k]; A[k]=v; QUICKSORT(m,k-1); QUICKSORT(k+1,p); } } void count(int x,int y,void process(int,int)) //计算运行时间 { int h1,h2,m1,m2,s1,s2,t1,t2,temp; struct _timeb timebuffer; struct tm *newtime; time_t long_time; time( long_time ); newtime = localtime( long_time ); //得到初始时的时间 h1=newtime-tm_hour; m1=newtime-tm_min; s1=newtime-tm_sec; _ftime( timebuffer ); t1=timebuffer.millitm; process(x,y); time( long_time ); newtime = localtime( long_time ); //得到结束时的时间 h2=newtime-tm_hour; m2=newtime-tm_min; s2=newtime-tm_sec; _ftime( timebuffer ); t2=timebuffer.millitm; temp=24*60*1000*(h2-h1)+60000*(m2-m1)+1000*(s2-s1)+t2-t1;//求时间差,即运行时间 printf(\t\t%5d ms,temp); } void main() { int i; A[MAX+1]=INT_MAX; printf(\t\tMERGESORT\t\tQUICKSORT\n); printf(Rand:); //随机时的比较 for(i=1;i=MAX;i++) C[i]=A[i]=rand(); count(1,MAX,MERGESORT); for(i=1;i=MAX;i++) B[i]=A[i]; for(i=1;i=MAX;i++) A[i]=C[i]; count(1,MAX,QUICKSORT);