大数据结构课程设计十种排序算法比较

1/18 2014~2015学年第学期课程数据结构与算法 学生某某学号 专业班级 指导教师2015年1月2/18 任务定义各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比拟各算法的关键字比拟次数和关键字移动次数，以取得直观感受。根据对本设计任务要求的理解和分析，按以下两点问题进展分析：题目要求对十种排序算法进展比拟，比拟的主要内容是关键字的比拟次数和移动次数，二、数据结构的选择和概要设计typedefintKeyType;structrec{KeyTypekey;typedefrecsqlist[N];2.主程序与各模块之间的关系是：(1)voidgensort(intb[],intn)起泡排序(2)voidinsertsort(sqlistb,intn)插入排序(3)voidso(sqlistnum,intn)折半插入排序(4)voidshellsort(sqlistb,intn)希尔排序(5)voidgentsort(intb[],intn)选择排序(6)voidoutput(sqlistb,intn)快速排序(7)voidsort3(sqlistnu,intn)//2-路插入排序(8)voidMerge(sqlista,sqlistb,intlow,intmid,inthigh)二路归并排序(9)voidMergePass(sqlista,sqlistb,intn,intlenth)一趟归并排序(10)voidMergeSort(sqlista,intn)//进展二路归并(11)voidsift(sqlistr,ints,intm)堆排序块，以上展示各个模块的功能，以下将分析主函数和各个模块中的具体算法和实现。函数声明：voidgensort(intb[],intn)起泡排序的根本思想是将第一个记录的关键字和第二个记录的关键字进展泡排序是一种稳定的排序方法，在随机产生数的情况下，总的时间复杂度为3/18 现子序列，在子序列内分别进展直接插入排序，然后不断缩小增量直至为1，最后使用直接插成排序。二分排序法的根本思想是：在插入第i个元素时，对前面的0~(i-1)个元24/18 堆中只有一个记录为止。堆排序是一种不稳定的排序方法，总的时间复杂度为2函数声明：voidMerge(sqlista,sqlistb,intlow,intmid,inthigh)voidMergePass(sqlista,sqlistb,intn,intlenth)voidMergeSort(sqlista,intn)合并排序：这里的合并排序和下边要描述的快速排序都采用了分而治之的思想，但两者仍然有很大差异。合并排序是将一个无序数组n[1…r]分成两个数组n[1…r/2]与n[r/2+1…r]，分别对这两个小数组进展合并排序，然后再将这两之后的有序序列中。先将待排序记录的关键字和d[1]的关键字比拟，假如L.r[i].key<d[1].ke如y,此将L.r[i]插入到d[1]之前的有序表中。反之，将Lridi后的有序表中。在实现算法时，将d看成一个循环向量，并将两个指针first和final分别指示排序过程中得到的有序序列中的第一个记录和最后一个记录在d中的位置。测试结果:2结果分析5/186/18 文献以上是对本设计的实现功能和算法等的全面分析，以下是带注释的源代码算法#include<iostream.h>#include<iomanip.h>#include<stdlib.h>#include<stdio.h>#include<time.h>#defineN100//起泡排序voidgensort(intb[],intn){ijintstfor(i=0;i<n-1;i++){for(j=i+1;j<n;j++){t++;{b[i]=b[j];b[j]=temp;cout<<"移动次数="<<s<<","<<"比拟次数="<<t<<endl;}//插入排序typedefintKeyType;structrec7/18 {KeyTypekey;typedefrecsqlist[N];voidinsertsort(sqlistb,intn){ijintstfor(i=2;i<n;i++){b[0].key=b[i].key;ji-1;t++;while(b[0].key<b[j].key){b[j+1]=b[j];j--;t++;}b[j+1]=b[0];}cout<<"移动次数="<<s<<","<<"比拟次数="<<t<<endl;}//折半插入排序voidso(sqlistnum,intn){intlow,high,m;//分别指向低、高、中的位置for(i=1;i<n;i++){t=num[i].key;while(low<=high)8/18 {m=(low+high)/2;elselow=m+1;}for(j=i-1;j>=high+1;j--){num[j+1].key=num[j].key;}num[high+1].key=t;}cout<<"移动次数="<<s<<","<<"比拟次数="<<k<<endl;}//希尔排序voidshellsort(sqlistb,intn){gap=n/2;while(gap>0){for(i=gap+1;i<n;i++){9/18 while(j>0){t++;if(b[j].key>b[j+gap].key){x=b[j];b[j]=b[j+gap];b[j+gap]=x;j=j-gap;}elsej=0;gap=gap/2;cout<<"移动次数="<<s<<","<<"比拟次数="<<t<<endl;//选择排序voidgentsort(intb[],intn){for(i=0;i<n-1;i++){for(j=i+1;j<n;j++){t++;}b[k]=b[i];b[i]=temp;cout<<"移动次数="<<s<<","<<"比拟次数="<<t<<endl;}//快速排序voidoutput(sqlistb,intn)//输出元素值{/18 for(inti=0;i<n;i++)cout<<setw(4)<<b[i].key;cout<<endl;}voiddisplay(intn,intm)//输出计数{cout<<"移动次数="<<n<<","<<"比拟次数="<<m<<endl;}voidBeforeSort()//初始化计数器{p=0;q=0;}voidquicksort(sqlistr,ints,intt){{r[0]=r[s];p++;while(i<j){pwhile(i<j&&r[j].key>=r[0].key)j--;rirj;q+;ppwhile(i<j&&r[i].key<=r[0].key)r[j]=r[i];q++;p++;}r[i]=r[0];p++;}elsereturn;quicksort(r,s,j-1);quicksort(r,j+1,t);}voidsort(sqlistr,ints,intt){BeforeSort(); quicksort(r,s,t);display(p,q);}//2-路插入排序voidsort3(sqlistnu,intn)#definemax20intfirst,final;//头尾指针intcache[max+1];//中转站for(i=0;i<n;i++){{first=0;final=0;cache[0]=nu[0].key;}lse{if(nu[i].key>=cache[final])final++;/18 cache[final]=nu[i].key;}elseif(nu[i].key<=cache[first])tfirstnfirst--;cache[first]=nu[i].key;}sefor(j=first;nu[i].key>cache[j];){cache[n-1]=cache[0];lsecache[j-1]=cache[j];s++;j++;}if(0==first)first=n-1; elsefirst--;cache[j-1]=nu[i].key;}}}for(i=first,j=0;j<n;j++){nu[j].key=cache[i];}cout<<"移动次数="<<s<<","<<"比拟次数="<<t<<endl;}//二路归并voidMerge(sqlista,sqlistb,intlow,intmid,inthigh){inti=low,j=mid+1,k=low;while((i<=mid)&&(j<=high)){ifa[i].key<=a[j].key){b[k++]=a[i++];g;/18 ++i;}lse{b[k++]=a[j++];g;++j;}++k;}//if(i<=mid)while(i<=mid)g;}//elsewhile(j<=high)g;}}//进展一趟归并voidMergePass(sqlista,sqlistb,intn,intlenth){while(i<=n-2*lenth){Merge(a,b,i,i+lenth-1,i+2*lenth-1);}nth/18/18 {Merge(a,b,i,i+lenth-1,n-1);}lsefor(k=i;k<=n-1;k++)g;}}//进展二路归并voidMergeSort(sqlista,intn)//int*b=(int*)malloc(n*sizeof(int));while(lenth<n/2+1){MergePass(a,b,n,lenth);MergePass(b,a,n,lenth);}cout<<"移动次数="<<g<<","<<"比拟次数="<<h<<endl;}//堆排序voidsift(sqlistr,ints,intm){x=r[s];for(j=2*s;j<=m;j*=2)if(j<m&&(r[j].key<r[j+1].key))++j;/18 q+;if(!(x.key<r[j].key))break;r[s]=r[j];s=j;p++;}rsxp+;}voidheapsort(sqlist&r,intm){sift(r,i,m);{w=r[i];r[i]=r[1];p3;sift(r,1,i-1);}}voidsorting(sqlist&r,intt){BeforeSort();heapsort(r,t);display(p,q);}{//#defineN100;srand((unsignedint)time(NULL));for(i=0;i<N;i++)a[i]=rand()%99+1;}voidmain(){/18 sqlista,b,c,d,num,R,nu,a2,b2;ighinita//随机产生个数for(i=0;i<N;i++){c1[i]=a1[i];a[i].key=a1[i];b[i].key=a1[i];c[i].key=a1[i];d[i].key=a1[i];num[i].key=a1[i];R[i].key=a1[i];nu[i].key=a1[i];dat[i]=a1[i];}cout<<"排序前数组:\n";for(i=0;i<N;i++)cout<<setw(4)<<a1[i];cout<<endl;cout<<"起泡排序运行结果:\n";gensort(a1,sizeof(a1)/sizeof(int));cout<<"插入排序运行结果