计算机学院0101班吴晴 学号200101183000 算法程序设计 一,比较归弄分奏和快速分类算油 思想:结合课本中的算法结构,分别计算在数据集相同且分别为随机 数,非降序,非增序情况下两种算法所需的时间.数据集为10000 dio. h> #include<conio. h> #include<stdlib. h #includestime h> #include<sys/timeb. h> #includeslimits. h> #define mAX 1000000 工作数据集为100000 int A[MAX+21 ∥多出的两个为0号和最后一个无穷大 int B[MAX+2] B和C保证排序使用的数据集相同,若作为局部变量会造成 int C[MAX+2 ∥存溢出 void mERGESORT(int low, int high) /归并排序 i int mid if(low<high) i mid=(low+high)/2 MERGESORT(low, mid) MERGESORT(mid+l, high) MERGE(low, mid, high); void merge( nt low, int mid int high)∥归并两个已分类的集合 k. h while(h<=mid&&j<=high) if(A[h]<=A[]){B[=A[h],h++; else( BGFA0: j++ if(h>mid)for(k-j, k<=high k++)B0=A(k]; 1++ else for(k=h k<=mid; k++)B=Ak i++;) for(k=low; k<=high; k++)A[k]=B(kI return void QUICKSORT(int m, int p) ∥快速排序将两个函数合为一个 int v, i, k, temp计算机学院 0101 班 吴晴 学号:2001011830002 1/5 算法程序设计 一,比较归并分类和快速分类算法 思想:结合课本中的算法结构,分别计算在数据集相同且分别为随机 数,非降序,非增序情况下两种算法所需的时间.数据集为 1000000. #include<stdio.h> #include<conio.h> #include<stdlib.h> #include<time.h> #include<sys/timeb.h> #include<limits.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(low<high) { 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<=mid&&j<=high) { if(A[h]<=A[j]) { B[i]=A[h]; h++; } else { B[i]=A[j]; j++; } i++; } if(h>mid) 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;